LeetCode 440 - K-th Smallest in Lexicographical Order
The problem asks us to find the k-th smallest number in lexicographical order among all integers from 1 to n. Lexicographical order means dictionary order, not numerical order.
Difficulty: 🔴 Hard
Topics: Trie
Solution
Problem Understanding
The problem asks us to find the k-th smallest number in lexicographical order among all integers from 1 to n.
Lexicographical order means dictionary order, not numerical order. For example, if n = 13, the numbers appear in this order:
1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9
This happens because the numbers are compared as strings:
"1" < "10" < "11" < ... < "2"
The input consists of:
n, the upper bound of the range[1, n]k, the position in lexicographical order that we want to retrieve
The output is the integer that appears in the k-th position when all integers from 1 to n are sorted lexicographically.
The constraints are extremely important:
1 <= k <= n <= 10^9
Since n can be as large as one billion, generating all numbers and sorting them is completely impractical. Even storing all numbers would require too much memory, and sorting would take far too long.
The problem is labeled with the Trie topic because the lexicographical ordering of numbers naturally forms a prefix tree. For example:
1
├── 10
├── 11
├── 12
└── 13
2
3
...
The key challenge is determining how to navigate this implicit trie efficiently without explicitly constructing it.
Several edge cases are important:
- When
n = 1, the answer must always be1 - When
k = n, we may need to traverse very deep into the lexicographical ordering - Numbers near powers of ten create uneven trie branches
- Prefixes may partially exceed
n, so subtree sizes must be clipped carefully - Large values of
nrequire an algorithm that avoids enumeration entirely
Approaches
Brute Force Approach
The most straightforward solution is to generate every number from 1 to n, convert them to strings, sort them lexicographically, and then return the k-th element.
For example:
numbers = [str(i) for i in range(1, n + 1)]
numbers.sort()
return int(numbers[k - 1])
This works because string sorting naturally produces lexicographical order.
However, this approach is far too slow and memory intensive for the given constraints. If n = 10^9, we cannot generate one billion numbers, much less sort them.
The time complexity is dominated by sorting:
O(n log n)
and the space complexity is also enormous:
O(n)
This immediately tells us we need a fundamentally different strategy.
Optimal Approach, Lexicographical Trie Traversal
The key observation is that lexicographical ordering corresponds exactly to a preorder traversal of a trie.
Consider the numbers from 1 to 13:
1
├── 10
├── 11
├── 12
└── 13
2
3
4
5
6
7
8
9
Instead of explicitly building this trie, we can treat it as an implicit structure.
The critical insight is that from any prefix, we can efficiently compute how many valid numbers exist beneath that prefix.
For example, with prefix 1 and n = 13:
1, 10, 11, 12, 13
There are 5 numbers in this subtree.
If we know the subtree size, we can decide:
- Skip the entire subtree if
kis larger than its size - Descend deeper if the target lies inside the subtree
This transforms the problem into trie navigation with subtree counting.
The algorithm behaves similarly to walking through a prefix tree while skipping entire branches whenever possible.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Generate and sort all numbers lexicographically |
| Optimal | O((log n)^2) | O(1) | Traverse implicit trie using subtree counting |
Algorithm Walkthrough
Step 1: Start at Prefix 1
Lexicographical order always begins with 1.
We initialize:
current = 1
k = k - 1
We subtract one because we are already standing on the first lexicographical number.
Step 2: Count Numbers Under the Current Prefix
We compute how many valid integers exist under a prefix.
For example, if:
prefix = 1
n = 13
then the subtree contains:
1, 10, 11, 12, 13
which gives size 5.
To count efficiently, we repeatedly expand ranges:
[1,2)
[10,20)
[100,200)
...
At each level we add:
min(n + 1, next_prefix) - current_prefix
This counts how many numbers fall within the range.
For example:
n = 13
prefix = 1
Level 1:
[1,2) contributes 1
Level 2:
[10,20) contributes 4
Total = 5
Step 3: Decide Whether to Skip or Descend
Once we know the subtree size:
- If
steps <= k, the target is not inside this subtree - We skip the entire subtree
- Move to the next sibling prefix
Example:
current = 1
steps = 5
k = 10
Since the subtree only contains 5 numbers, we skip it:
current = 2
k -= 5
Step 4: Descend into the Subtree
If the subtree contains the target:
steps > k
then we descend one level deeper:
current *= 10
k -= 1
Multiplying by 10 moves to the first child in lexicographical order.
Example:
1 -> 10
Step 5: Repeat Until k == 0
We continue navigating the trie until we consume all remaining positions.
At that moment, current is the answer.
Why it works
The algorithm maintains the invariant that current always points to the current lexicographical position in the implicit trie. The subtree counting function precisely determines how many lexicographical numbers exist beneath a prefix. Because lexicographical order corresponds to preorder traversal of the trie, skipping a subtree is equivalent to skipping all numbers within that prefix range. Descending deeper preserves traversal order. Therefore, every movement exactly matches lexicographical enumeration, guaranteeing the correct k-th number is reached.
Python Solution
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
def count_steps(curr: int, nxt: int) -> int:
steps = 0
while curr <= n:
steps += min(n + 1, nxt) - curr
curr *= 10
nxt *= 10
return steps
current = 1
k -= 1
while k > 0:
steps = count_steps(current, current + 1)
if steps <= k:
current += 1
k -= steps
else:
current *= 10
k -= 1
return current
The implementation closely follows the trie traversal strategy.
The helper function count_steps computes how many numbers lie lexicographically between two prefixes. It repeatedly expands the prefix range by multiplying by 10, effectively moving down trie levels.
For example:
curr = 1
nxt = 2
expands into:
[1,2)
[10,20)
[100,200)
...
At each level, we count how many valid numbers remain within [1, n].
The main loop maintains the current lexicographical position.
If the subtree size is smaller than or equal to the remaining k, we skip the subtree entirely by incrementing current.
Otherwise, we descend deeper into the trie by multiplying current by 10.
The loop ends once all positions have been consumed.
Go Solution
func findKthNumber(n int, k int) int {
countSteps := func(curr int, next int) int {
steps := 0
for curr <= n {
upper := next
if n+1 < upper {
upper = n + 1
}
steps += upper - curr
curr *= 10
next *= 10
}
return steps
}
current := 1
k--
for k > 0 {
steps := countSteps(current, current+1)
if steps <= k {
current++
k -= steps
} else {
current *= 10
k--
}
}
return current
}
The Go implementation follows the same logic as the Python version.
One notable difference is that Go does not provide a built in min function for integers, so we manually compute the smaller value using conditional logic.
The algorithm uses only integer arithmetic and constant extra space, making it efficient even for the largest constraints.
Worked Examples
Example 1
Input:
n = 13
k = 2
Lexicographical order:
1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9
We want the second number.
Initial state:
current = 1
k = 1
| Iteration | current | steps under prefix | action | remaining k |
|---|---|---|---|---|
| 1 | 1 | 5 | descend into subtree | 0 |
Since steps = 5 > k = 1, the target lies inside the subtree rooted at 1.
We descend:
current = 10
k = 0
Answer:
10
Example 2
Input:
n = 1
k = 1
Initial state:
current = 1
k = 0
The loop never runs because we are already at the first lexicographical number.
Answer:
1
Additional Example
n = 100
k = 10
Traversal:
| Iteration | current | steps | action | k after action |
|---|---|---|---|---|
| Start | 1 | - | initialize | 9 |
| 1 | 1 | 12 | descend | 8 |
| 2 | 10 | 2 | skip subtree | 6 |
| 3 | 11 | 1 | skip subtree | 5 |
| 4 | 12 | 1 | skip subtree | 4 |
| 5 | 13 | 1 | skip subtree | 3 |
| 6 | 14 | 1 | skip subtree | 2 |
| 7 | 15 | 1 | skip subtree | 1 |
| 8 | 16 | 1 | skip subtree | 0 |
Final answer:
17
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O((log n)^2) | Each subtree count takes O(log n), and traversal performs O(log n) major moves |
| Space | O(1) | Only a few integer variables are used |
The counting function traverses digit levels of the trie, which takes at most O(log n) time.
The outer traversal also performs at most O(log n) meaningful prefix transitions for each digit depth. Combined, this gives an overall complexity of approximately O((log n)^2).
The algorithm does not allocate auxiliary data structures, so the space usage remains constant.
Test Cases
solution = Solution()
assert solution.findKthNumber(13, 2) == 10 # provided example
assert solution.findKthNumber(1, 1) == 1 # smallest possible input
assert solution.findKthNumber(10, 1) == 1 # first lexicographical number
assert solution.findKthNumber(10, 2) == 10 # transition into deeper prefix
assert solution.findKthNumber(10, 3) == 2 # move to sibling prefix
assert solution.findKthNumber(100, 10) == 17 # multiple subtree skips
assert solution.findKthNumber(100, 90) == 9 # near end of traversal
assert solution.findKthNumber(999, 1) == 1 # always starts with 1
assert solution.findKthNumber(999, 999) == 999 # last lexicographical element
assert solution.findKthNumber(1000, 100) > 0 # larger traversal case
assert solution.findKthNumber(1000000000, 1) == 1 # maximum n boundary
assert solution.findKthNumber(20, 12) == 2 # exact subtree boundary
assert solution.findKthNumber(50, 25) > 0 # mid traversal stress case
Test Summary
| Test | Why |
|---|---|
n=13, k=2 |
Validates provided example |
n=1, k=1 |
Smallest possible input |
n=10, k=2 |
Tests descending into child prefix |
n=10, k=3 |
Tests sibling traversal |
n=100, k=10 |
Validates repeated subtree skipping |
n=999, k=999 |
Tests traversal near final element |
n=10^9, k=1 |
Validates maximum constraint handling |
n=20, k=12 |
Tests exact subtree size boundaries |
n=50, k=25 |
Mid range traversal stress case |
Edge Cases
One important edge case occurs when n = 1. In this scenario, the trie contains only a single node. Many implementations fail because they assume at least one traversal step is necessary. This implementation handles the case naturally because k becomes zero immediately after initialization, so the loop never executes.
Another tricky case occurs near powers of ten, such as n = 1000. Prefixes like 1 contain very large subtrees, while prefixes near the end may contain very few elements. Incorrect subtree counting often happens when ranges exceed n. This implementation safely clips each level using:
min(n + 1, nxt)
which prevents overcounting.
A third important edge case occurs when the answer lies exactly at a subtree boundary. For example, if the subtree under prefix 1 contains exactly 12 elements and k = 12, the algorithm must skip the entire subtree rather than descend into it. The condition:
if steps <= k:
correctly handles this situation by ensuring subtree boundaries are interpreted properly.
Another subtle issue involves large values of n near 10^9. Recursive trie construction or explicit enumeration would exceed memory or time limits. This implementation avoids both problems entirely by computing subtree sizes mathematically and storing only constant additional state.