#386

Medium

auto_awesomeDepth-First Search plus Trie

LeetCode Problem Workspace

Lexicographical Numbers

Generate all numbers from 1 to n in lexicographical order using a depth-first search pattern optimized with trie logic for efficiency.

depth first search trie

Problem Statement

Given an integer n, return all integers in the range [1, n] sorted in lexicographical order. Your solution must efficiently generate the sequence without using built-in sorting methods.

Design an algorithm that uses depth-first search to traverse numbers as if building a trie of digits. The algorithm should achieve O(n) time complexity with O(1) extra space, outputting the full lexicographical list.

Examples

Example 1

Input: n = 13

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

Example details omitted.

Example 2

Input: n = 2

Output: [1,2]

Example details omitted.

Constraints

1 <= n <= 5 * 104

Solution Approach

Recursive Depth-First Search with Prefix Expansion

Begin with numbers 1 through 9 and recursively append digits 0 through 9 to each prefix. Stop recursion when the generated number exceeds n. This DFS traversal mimics a trie structure where each node represents a digit prefix.

Iterative Simulation of Trie Traversal

Instead of using recursion stack, maintain a current number and repeatedly multiply by 10 to explore deeper prefixes. When reaching a number larger than n, increment and trim trailing zeros to move to the next lexicographical number.

Avoid Extra Space Beyond Output List

Do not construct a full tree or additional arrays. Only track the current number during traversal. This approach ensures O(1) extra space while the output list naturally accumulates numbers in lexicographical order.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each number from 1 to n is visited exactly once during DFS traversal. Space complexity is O(1) beyond the output list since only a single integer is tracked during iteration or recursion, avoiding extra data structures.

What Interviewers Usually Probe

Asks how to generate numbers without sorting the final list.
Checks understanding of DFS traversal applied to number prefixes.
Tests ability to optimize space usage for large n values.

Common Pitfalls or Variants

Common pitfalls

Forgetting to stop recursion when the number exceeds n.
Using built-in sort instead of generating numbers lexicographically.
Exceeding space limits by storing unnecessary intermediate data structures.

Follow-up variants

Generate numbers in reverse lexicographical order using the same DFS-trie pattern.
Limit the output to numbers containing a specific digit while maintaining lexicographical order.
Adapt the approach for a range [m, n] instead of starting from 1, adjusting prefix exploration accordingly.

FAQ

What is the key pattern for solving Lexicographical Numbers?

The problem uses a depth-first search pattern combined with trie-like prefix expansion to generate numbers lexicographically.

Can this be solved without recursion?

Yes, iterative traversal multiplying by 10 and adjusting numbers simulates the DFS-trie pattern without recursion, preserving O(1) space.

Why can't we just sort numbers from 1 to n?

Sorting adds O(n log n) time and extra space, whereas DFS-trie traversal achieves O(n) time and minimal space.

What are common mistakes in this problem?

Exceeding n during recursion, forgetting to handle trailing zeros, or using extra arrays for prefixes are typical pitfalls.

Does this pattern work for very large n, like 50000?

Yes, following the DFS-trie approach carefully ensures O(n) traversal with O(1) extra space, suitable even for the upper constraint.

terminal

Solution

Solution 1: Iteration

We first define a variable $v$, initially $v = 1$. Then we start iterating from $1$, adding $v$ to the answer array each time. Then, if $v \times 10 \leq n$, we update $v$ to $v \times 10$; otherwise, if $v \bmod 10 = 9$ or $v + 1 > n$, we loop to divide $v$ by $10$. After the loop ends, we increment $v$. Continue iterating until we have added $n$ numbers to the answer array.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans = []
        v = 1
        for _ in range(n):
            ans.append(v)
            if v * 10 <= n:
                v *= 10
            else:
                while v % 10 == 9 or v + 1 > n:
                    v //= 10
                v += 1
        return ans

Continue Practicing

#472 concatenated words #211 design add and search words data structure #676 implement magic dictionary