Watch 10 video solutions for Lexicographical Numbers, a medium level problem involving Depth-First Search, Trie. This walkthrough by NeetCodeIO has 19,819 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Input: n = 13 Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2 Output: [1,2]
Constraints:
1 <= n <= 5 * 104Problem Overview: Given an integer n, return the numbers from 1 to n sorted in lexicographical (dictionary) order. The challenge is generating this order without converting all numbers to strings and sorting them, which would add unnecessary overhead.
Approach 1: DFS Prefix Traversal (O(n) time, O(h) space)
This problem maps naturally to a Trie-like prefix tree. Each number is treated as a prefix, and its children are formed by appending digits 0-9. Starting from prefixes 1 through 9, perform a depth-first traversal and keep expanding by multiplying the current number by 10 and adding digits. If the generated value exceeds n, stop exploring that branch. This produces numbers exactly in lexicographical order because DFS always explores the smallest prefix first.
The recursion depth corresponds to the number of digits in n, making the auxiliary space O(h) where h ≈ log10(n). This method is conceptually simple and mirrors how a Trie organizes numbers by prefixes. It’s also a clean application of Depth-First Search.
Approach 2: Iterative Lexicographical Traversal (O(n) time, O(1) space)
The iterative solution simulates the same prefix traversal without recursion. Start with current = 1. At each step, append the current number to the result. If current * 10 ≤ n, move to the smallest child (go deeper in the prefix tree). Otherwise, move to the next sibling by incrementing current. If the increment causes a trailing zero boundary or exceeds n, repeatedly divide by 10 until a valid next prefix is found.
This logic mimics walking through an implicit trie in lexicographical order. Instead of storing the tree, you navigate it using arithmetic operations like *10, +1, and /10. Every number from 1 to n is visited exactly once, giving O(n) time complexity while keeping extra space constant.
Recommended for interviews: Interviewers typically expect the iterative prefix traversal. It demonstrates understanding of lexicographical ordering and avoids recursion overhead, achieving O(n) time and O(1) extra space. The DFS approach is still valuable because it clearly shows the underlying trie structure and confirms your understanding of the traversal pattern.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Prefix Traversal | O(n) | O(h) recursion stack | When you want a clear conceptual mapping to a trie or DFS traversal of prefixes |
| Iterative Lexicographical Traversal | O(n) | O(1) extra space | Preferred for interviews and production due to constant space and direct traversal |