Coding Interview PatternsLexicographical Numbers
MediumTrie
Lexicographical Numbers
Explanation & Solution
Description
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.
Input: n = 13
Output:[1,10,11,12,13,2,3,4,5,6,7,8,9]
0
1
1
10
2
11
3
12
4
13
5
2
6
3
7
4
8
5
9
6
10
7
11
8
12
9
Explanation: The numbers from 1 to 13 sorted lexicographically (as strings) are [1,10,11,12,13,2,3,4,5,6,7,8,9].
Constraints
1 <= n <= 5 * 10^4
Approach
Trie pattern
1. Think of Numbers as a Trie (10-ary Tree)
- Imagine a trie where each node represents a digit prefix
- The root has children 1-9, each node has children 0-9
- Lexicographical order is simply a pre-order DFS traversal of this trie
2. Initialize the Traversal
- Start with
curr = 1(the first number in lexicographical order) - We will collect exactly
nnumbers into the result array
3. Go Deeper (Multiply by 10)
- If
curr * 10 <= n, we can go deeper in the trie - Multiply
currby 10 to visit the next level (e.g., from 1 to 10)
4. Go to Next Sibling or Backtrack
- If we cannot go deeper, try the next sibling by incrementing
curr - If
curr >= n, we need to backtrack first by dividing by 10 - After incrementing, remove any trailing zeros (e.g., going from 19+1=20 is fine, but 199+1=200 needs to become 2)
5. Repeat Until All Numbers Are Collected
- Continue the loop for exactly
niterations - Each iteration adds one number in lexicographical order
Key Insight
- The lexicographical ordering of numbers maps perfectly to a pre-order DFS on a 10-ary trie
- By simulating this DFS iteratively with multiply/divide/increment operations, we achieve O(n) time and O(1) extra space (excluding output)