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:

[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

Example function shape:

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

Examples

Example 1:

n = 13

If we compare numbers as strings, the order is:

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

So the answer is:

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

Example 2:

n = 2

The numbers are:

[1, 2]

So the answer is:

[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.

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:

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

Each number can have children formed by appending one digit:

x * 10 + digit

For example, the children of 12 are:

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:

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:

   curr *= 10
3. Otherwise, we cannot go deeper.
4. While curr ends in 9, or curr + 1 > n, move up:

   curr //= 10
5. Then move to the next sibling:

   curr += 1

The while loop handles cases like:

19 -> 2

and:

13 -> 2     when n = 13

Walkthrough

Let:

n = 13

Start:

curr = 1

Append 1.

Since 1 * 10 <= 13, go deeper:

curr = 10

Append 10.

Cannot go to 100, so increment:

curr = 11

Then:

11 -> 12 -> 13

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

13 // 10 = 1

Now we can increment:

1 + 1 = 2

Then the order continues:

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

So the result is:

[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:

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

Each node x has children:

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

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

Implementation

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:

curr = 1

The loop runs exactly n times:

for _ in range(n):

Each iteration appends one number:

ans.append(curr)

If possible, we go deeper in the digit tree:

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

This handles transitions like:

1 -> 10
10 -> 100

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

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

Then we move to that sibling:

curr += 1

Finally, return the generated order:

return ans

Testing

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: