# LeetCode 386: Lexicographical Numbers

## Problem Restatement

We are given an integer `n`.

We need to return all numbers from `1` to `n` in lexicographical order.

Lexicographical order means dictionary order, as if the numbers were strings.

For example, when `n = 13`, the numbers are ordered like this:

```python
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
```

The problem asks for an algorithm that runs in `O(n)` time and uses `O(1)` extra space, not counting the output array.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | List of integers from `1` to `n` in lexicographical order |
| Constraint | `1 <= n <= 5 * 10^4` |
| Required time | `O(n)` |
| Required extra space | `O(1)` excluding output |

Example function shape:

```python
def lexicalOrder(n: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
n = 13
```

If we compare numbers as strings, the order is:

```text
"1", "10", "11", "12", "13", "2", "3", ..., "9"
```

So the answer is:

```python
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
```

Example 2:

```python
n = 2
```

The numbers are:

```python
[1, 2]
```

So the answer is:

```python
[1, 2]
```

## First Thought: Convert to Strings and Sort

A direct solution is:

1. Generate all numbers from `1` to `n`.
2. Sort them by their string form.
3. Return the sorted numbers.

```python
class Solution:
    def lexicalOrder(self, n: int) -> list[int]:
        nums = list(range(1, n + 1))
        nums.sort(key=str)
        return nums
```

This is easy to understand, but sorting costs `O(n log n)` time.

The problem asks for `O(n)` time, so we need to generate the numbers directly in lexicographical order.

## Key Insight

Lexicographical order behaves like a preorder traversal of a digit tree.

Think of numbers as prefixes.

From `1`, the next lexicographical numbers are:

```text
1
10
100
101
102
...
11
12
...
19
2
20
...
```

Each number can have children formed by appending one digit:

```python
x * 10 + digit
```

For example, the children of `12` are:

```python
120, 121, 122, 123, 124, 125, 126, 127, 128, 129
```

as long as they do not exceed `n`.

So the lexicographical order is the same as walking this implicit tree in preorder.

We can simulate that traversal with one variable `curr`.

## Algorithm

Start with:

```python
curr = 1
```

Repeat exactly `n` times, because we need to output `n` numbers.

At each step:

1. Append `curr` to the answer.
2. If `curr * 10 <= n`, go deeper:
   ```python id="za54df"
   curr *= 10
   ```
3. Otherwise, we cannot go deeper.
4. While `curr` ends in `9`, or `curr + 1 > n`, move up:
   ```python id="knq65b"
   curr //= 10
   ```
5. Then move to the next sibling:
   ```python id="jd7ezr"
   curr += 1
   ```

The `while` loop handles cases like:

```text
19 -> 2
```

and:

```text
13 -> 2     when n = 13
```

## Walkthrough

Let:

```python
n = 13
```

Start:

```python
curr = 1
```

Append `1`.

Since `1 * 10 <= 13`, go deeper:

```python
curr = 10
```

Append `10`.

Cannot go to `100`, so increment:

```python
curr = 11
```

Then:

```text
11 -> 12 -> 13
```

After `13`, we cannot go deeper, and `14 > 13`, so we move up:

```python
13 // 10 = 1
```

Now we can increment:

```python
1 + 1 = 2
```

Then the order continues:

```text
2, 3, 4, 5, 6, 7, 8, 9
```

So the result is:

```python
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
```

## Correctness

The numbers from `1` to `n` form an implicit digit tree.

Each root is one of:

```python
1, 2, 3, 4, 5, 6, 7, 8, 9
```

Each node `x` has children:

```python
x * 10, x * 10 + 1, ..., x * 10 + 9
```

as long as those values are at most `n`.

Lexicographical order is preorder traversal of this tree: visit the current number first, then visit its children from smallest digit to largest digit.

The algorithm follows exactly that traversal.

When `curr * 10 <= n`, the next lexicographical number is the first child of `curr`, so moving to `curr * 10` is correct.

When `curr` has no valid child, the next lexicographical number must be the next available sibling. If `curr` ends in `9`, it has no next sibling under the same parent. If `curr + 1 > n`, the next sibling would exceed the allowed range. In both cases, the algorithm moves up to the parent by dividing by `10`.

After moving up enough, `curr + 1` is the next valid sibling, so incrementing gives the next lexicographical number.

The loop appends exactly one number per iteration and runs `n` iterations. Since the traversal starts at `1` and always moves to the next lexicographical number, the output contains all numbers from `1` to `n` in the required order.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We append exactly `n` numbers |
| Space | `O(1)` extra | Only `curr` and loop variables are used |

The returned answer array has size `O(n)`, but the problem excludes it from extra space.

## Implementation

```python
class Solution:
    def lexicalOrder(self, n: int) -> list[int]:
        ans = []
        curr = 1

        for _ in range(n):
            ans.append(curr)

            if curr * 10 <= n:
                curr *= 10
            else:
                while curr % 10 == 9 or curr + 1 > n:
                    curr //= 10

                curr += 1

        return ans
```

## Code Explanation

We start from the first lexicographical number:

```python
curr = 1
```

The loop runs exactly `n` times:

```python
for _ in range(n):
```

Each iteration appends one number:

```python
ans.append(curr)
```

If possible, we go deeper in the digit tree:

```python
if curr * 10 <= n:
    curr *= 10
```

This handles transitions like:

```text
1 -> 10
10 -> 100
```

If we cannot go deeper, we backtrack until a next sibling exists:

```python
while curr % 10 == 9 or curr + 1 > n:
    curr //= 10
```

Then we move to that sibling:

```python
curr += 1
```

Finally, return the generated order:

```python
return ans
```

## Testing

```python
def test_solution():
    s = Solution()

    assert s.lexicalOrder(1) == [1]
    assert s.lexicalOrder(2) == [1, 2]
    assert s.lexicalOrder(13) == [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
    assert s.lexicalOrder(20) == [
        1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20,
        3, 4, 5, 6, 7, 8, 9,
    ]

    for n in [9, 10, 99, 100]:
        expected = sorted(range(1, n + 1), key=str)
        assert s.lexicalOrder(n) == expected

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Minimum input |
| `n = 2` | Simple two-number case |
| `n = 13` | Main example with `10` before `2` |
| `n = 20` | Checks transition from `19` to `2`, then `20` |
| Compare with string sort | Confirms lexicographical order for several boundaries |