LeetCode 386 - Lexicographical Numbers

The problem asks us to generate all integers from 1 to n, but not in normal numerical order. Instead, the numbers must appear in lexicographical order, also called dictionary order. Lexicographical order compares numbers as strings rather than as numeric values.

leetcodemediumdepth-first-searchtrie

LeetCode Problem 386

Difficulty: 🟡 Medium
Topics: Depth-First Search, Trie

Solution

Problem Understanding

The problem asks us to generate all integers from 1 to n, but not in normal numerical order. Instead, the numbers must appear in lexicographical order, also called dictionary order.

Lexicographical order compares numbers as strings rather than as numeric values. For example:

  • "1" comes before "10"
  • "10" comes before "11"
  • "2" comes after "13"

If n = 13, the lexicographical ordering becomes:

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

The input is a single integer n, representing the upper bound of the range [1, n].

The output must contain every integer in that range exactly once, sorted lexicographically.

The important part of this problem is not simply producing the correct ordering, but doing so under strict complexity requirements:

  • Time complexity must be O(n)
  • Extra space complexity must be O(1)

These constraints immediately eliminate solutions that convert numbers to strings and sort them directly, because sorting requires O(n log n) time and additional memory.

The constraint 1 <= n <= 5 * 10^4 is not extremely large, but the problem explicitly demands an optimal traversal strategy rather than relying on built in sorting.

Several edge cases are important:

  • n = 1, the smallest possible input
  • Numbers ending in 9, where traversal must backtrack correctly
  • Numbers where multiplying by 10 exceeds n
  • Transitions like 19 -> 2, which are not numerically adjacent but are lexicographically adjacent
  • Inputs like 100, where deep lexicographical branches exist

A naive implementation often fails during these transitions between prefixes.

Approaches

Brute Force Approach

The simplest approach is:

  1. Generate all integers from 1 to n
  2. Convert each integer to a string
  3. Sort the strings lexicographically
  4. Convert them back to integers

For example:

numbers = [1, 2, 3, ..., n]
numbers.sort(key=str)

This works because string comparison naturally follows lexicographical ordering.

However, sorting requires O(n log n) comparisons. Additionally, converting numbers to strings and storing them introduces extra memory overhead.

Although this solution is straightforward and correct, it violates the required O(n) time constraint.

Optimal Approach

The key insight is that lexicographical order forms a virtual tree structure.

For example, if n = 13:

1
├── 10
├── 11
├── 12
└── 13

2
3
4
...
9

Each number acts like a prefix.

From a current number:

  • Going deeper in the tree means multiplying by 10
  • Moving to the next sibling means adding 1
  • Backtracking means dividing by 10

This structure allows us to simulate a depth first traversal without explicitly building a trie or recursion stack.

The traversal rules are:

  1. Try to go deeper by multiplying by 10
  2. If not possible, move to the next sibling by adding 1
  3. If the sibling is invalid or ends in 9, backtrack until a valid sibling exists

This generates numbers directly in lexicographical order in exactly O(n) time and O(1) extra space.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Generate all numbers and sort them as strings
Optimal O(n) O(1) Simulates DFS traversal of a lexicographical tree

Algorithm Walkthrough

Step 1: Start From 1

Lexicographical order always begins with 1, so initialize:

current = 1

We will generate exactly n numbers.

Step 2: Add Current Number to Result

At every iteration, append the current number to the answer list.

This guarantees that numbers are recorded in traversal order.

Step 3: Try Going Deeper

The lexicographically smallest child of a number is obtained by appending a digit 0.

Mathematically:

current * 10

Example:

1 -> 10
10 -> 100

If current * 10 <= n, we move deeper:

current *= 10

This mirrors DFS traversal into the subtree.

Step 4: Move to Next Sibling

If going deeper is impossible, try moving horizontally.

Example:

10 -> 11
11 -> 12

This is done with:

current += 1

However, this only works if:

  • The next number does not exceed n
  • The current number does not end in 9

Step 5: Backtrack When Necessary

If:

  • current ends with 9, or
  • current + 1 > n

then we must move upward in the tree.

We repeatedly divide by 10:

current //= 10

until a valid sibling exists.

Example:

19 -> 1 -> 2

After backtracking, increment:

current += 1

Step 6: Repeat Until n Numbers Are Generated

We continue this traversal exactly n times.

Because each number is visited once, total complexity remains linear.

Why It Works

The algorithm performs a preorder DFS traversal of the implicit lexicographical tree.

At every step:

  • Multiplying by 10 visits the leftmost child
  • Incrementing visits the next sibling
  • Dividing by 10 backtracks to the parent

These operations exactly reproduce lexicographical ordering without explicitly storing the tree structure.

Since each number from 1 to n is generated once and only once, the algorithm is correct and optimal.

Python Solution

from typing import List

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        current = 1

        for _ in range(n):
            result.append(current)

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

                current += 1

        return result

The implementation starts with current = 1, which is always the first lexicographical number.

The loop runs exactly n times, ensuring every number is generated once.

Inside the loop:

  • The current number is appended to the result.
  • The algorithm first attempts to go deeper into the lexicographical tree by multiplying by 10.
  • If deeper traversal is impossible, the code backtracks until a valid sibling exists.
  • Finally, it moves to the next sibling using current += 1.

The while loop handles all cases where traversal must move upward in the tree, such as transitions from 19 -> 2 or 199 -> 2.

No recursion, sorting, or auxiliary data structures are used, which satisfies the required O(1) extra space constraint.

Go Solution

func lexicalOrder(n int) []int {
    result := make([]int, 0, n)
    current := 1

    for i := 0; i < n; i++ {
        result = append(result, current)

        if current*10 <= n {
            current *= 10
        } else {
            for current%10 == 9 || current+1 > n {
                current /= 10
            }

            current++
        }
    }

    return result
}

The Go implementation follows the same traversal logic as the Python version.

A slice with capacity n is preallocated for efficiency:

result := make([]int, 0, n)

Integer arithmetic in Go naturally handles all required operations safely because the constraint n <= 5 * 10^4 is far below overflow limits for int.

Unlike Python, Go does not have dynamic list resizing semantics identical to Python lists, so preallocating capacity avoids unnecessary reallocations.

Worked Examples

Example 1

Input:

n = 13

Expected output:

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

Step by Step Trace

Iteration Current Action Result
1 1 append 1, go deeper to 10 [1]
2 10 append 10, cannot go deeper, move to 11 [1,10]
3 11 append 11, move to 12 [1,10,11]
4 12 append 12, move to 13 [1,10,11,12]
5 13 append 13, backtrack to 1, move to 2 [1,10,11,12,13]
6 2 append 2, move to 3 [1,10,11,12,13,2]
7 3 append 3, move to 4 [1,10,11,12,13,2,3]
8 4 append 4, move to 5 [1,10,11,12,13,2,3,4]
9 5 append 5, move to 6 [1,10,11,12,13,2,3,4,5]
10 6 append 6, move to 7 [1,10,11,12,13,2,3,4,5,6]
11 7 append 7, move to 8 [1,10,11,12,13,2,3,4,5,6,7]
12 8 append 8, move to 9 [1,10,11,12,13,2,3,4,5,6,7,8]
13 9 append 9 [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2

Input:

n = 2

Expected output:

[1,2]

Step by Step Trace

Iteration Current Action Result
1 1 append 1, cannot go deeper, move to 2 [1]
2 2 append 2 [1,2]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each number from 1 to n is visited exactly once
Space O(1) Only a few integer variables are used beyond the output list

The traversal never revisits numbers or performs sorting operations.

Although the algorithm occasionally backtracks by dividing by 10, the total number of such operations across the entire execution is still linear relative to n.

The output list itself is not counted toward auxiliary space complexity because it is required by the problem.

Test Cases

from typing import List

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        current = 1

        for _ in range(n):
            result.append(current)

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

                current += 1

        return result

sol = Solution()

assert sol.lexicalOrder(1) == [1]  # minimum input
assert sol.lexicalOrder(2) == [1, 2]  # small sequential case
assert sol.lexicalOrder(9) == [1,2,3,4,5,6,7,8,9]  # single digit range
assert sol.lexicalOrder(10) == [1,10,2,3,4,5,6,7,8,9]  # first deep branch
assert sol.lexicalOrder(13) == [1,10,11,12,13,2,3,4,5,6,7,8,9]  # provided example
assert sol.lexicalOrder(19) == [1,10,11,12,13,14,15,16,17,18,19,2,3,4,5,6,7,8,9]  # backtracking from 19
assert sol.lexicalOrder(20) == [1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9]  # branch under 2
assert sol.lexicalOrder(99)[0] == 1  # starts correctly
assert sol.lexicalOrder(99)[-1] == 99  # ends correctly
assert len(sol.lexicalOrder(50000)) == 50000  # upper constraint stress test
Test Why
n = 1 Validates minimum boundary
n = 2 Validates small input behavior
n = 9 Ensures simple single digit ordering
n = 10 Tests transition into deeper lexicographical branch
n = 13 Validates provided example
n = 19 Tests backtracking after reaching 19
n = 20 Tests subtree traversal under prefix 2
n = 99 Verifies ordering across many branches
n = 50000 Stress test for upper constraint

Edge Cases

Edge Case 1: Smallest Possible Input

When n = 1, the answer contains only one number.

A buggy implementation might incorrectly attempt deeper traversal with 10 or perform unnecessary backtracking.

This implementation handles the case naturally because the loop executes once and appends only 1.

Edge Case 2: Transition From 19 to 2

This is one of the most important lexicographical transitions.

Numerically, 20 follows 19, but lexicographically 2 comes next.

A naive increment based solution would fail here.

The implementation correctly backtracks:

19 -> 1 -> 2

using repeated division by 10.

Edge Case 3: Numbers Ending in 9

Whenever the current number ends in 9, there are no more siblings at that level.

For example:

9
19
29
199

The algorithm detects this using:

current % 10 == 9

and backtracks until a valid next sibling exists.

Edge Case 4: Deep Branches Exceeding n

Suppose n = 13.

From 13, multiplying by 10 gives 130, which exceeds n.

The algorithm avoids invalid traversal with:

if current * 10 <= n:

This guarantees that only valid numbers are generated.