Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].
Example 1:
Input: n = 13, k = 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
Example 2:
Input: n = 1, k = 1 Output: 1
Constraints:
1 <= k <= n <= 109Problem Overview: Given integers n and k, return the k-th smallest number in lexicographical order within the range [1, n]. Instead of sorting numbers as strings (which would be expensive), you navigate the implicit dictionary order of numbers like a prefix tree.
Approach 1: Lexicographical Order Tree Traversal (O((log n)^2) time, O(1) space)
Numbers from 1 to n can be visualized as a prefix tree (similar to a trie) where each node represents a numeric prefix. For example, prefix 1 expands to 10, 11, 12.... Instead of generating all numbers, count how many values exist under a prefix using a helper function that measures the gap between two lexicographical prefixes.
Start at prefix 1. At each step, compute how many numbers lie under the current prefix. If the count is less than or equal to k, skip the entire subtree and move to the next prefix (like 1 → 2). Otherwise, go deeper into the tree (1 → 10). This approach simulates a preorder traversal of the lexicographical tree without building it explicitly. Because each prefix expansion and counting step takes about O(log n) time and you move through roughly log n levels, the overall complexity becomes O((log n)^2).
This technique is efficient even for very large n (up to 10^9) because it skips entire subtrees rather than enumerating numbers. Conceptually it combines ideas from trie traversal and prefix counting.
Approach 2: Binary Search with Counting Function (O((log n)^2) time, O(1) space)
Another strategy treats the lexicographical order as a searchable space and applies binary search. For a candidate number, compute how many numbers from 1..n appear before it in lexicographical order. This counting relies on the same prefix-range calculation used in the tree traversal approach.
Binary search repeatedly narrows the range until the number whose lexicographical rank equals k is found. Each rank computation walks through digit levels and counts valid prefixes, which costs O(log n). With O(log n) binary search iterations, the final complexity remains O((log n)^2).
The method is conceptually clean if you're comfortable with ranking functions, though the traversal approach usually results in simpler code.
Recommended for interviews: The lexicographical prefix traversal is the solution most interviewers expect. It demonstrates that you recognize the implicit 1..n lexicographical structure and can efficiently skip entire branches using prefix counts. A brute-force string sort would be O(n log n) and impractical for large inputs, while the prefix traversal shows strong algorithmic insight.
This approach involves systematically traversing a conceptual lexicographical tree. Each integer can be considered a node, with its child nodes being its successors in a lexicographical sense. By counting numbers in subtrees, we can determine where the k-th smallest number lies without generating the entire lexicographical list.
The given C implementation finds the k-th smallest number in a lexicographical manner using a tree traversal strategy. The helper function count_steps calculates how many numbers lie between the current root and its next sibling. This counting allows us to decide if we should move down to the next level (using the current root as a prefix) or move to the next sibling node.
Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level.
Space Complexity: O(1), since we are not using any additional data structures.
This approach leverages binary search combined with a counting function to directly determine the k-th lexicographical number. Instead of constructing the list, we estimate the position of the k-th number by adjusting potential candidates using the count of valid numbers below a mid-point candidate.
This C approach implements a binary search to find the k-th smallest lexicographical number. The count_below function determines how many numbers less than a given prefix exist. Depending on this count, we adjust our binary search to quickly converge on the result.
Time Complexity: O(log(n)^2), where binary search narrows down potential candidates.
Space Complexity: O(1), minimal variable storage is employed.
The problem asks for the \k\-th smallest number in the range [1, n] when all numbers are sorted in lexicographical order. Since n can be as large as 10^9, we cannot afford to generate and sort all the numbers explicitly. Instead, we adopt a strategy based on greedy traversal over a conceptual Trie.
We treat the range [1, n] as a 10-ary prefix tree (Trie):
0 \sim 9;1 has children 10, 11, ldots, 19, and node 10 has children 100, 101, ldots, 109;root
├── 1
│ ├── 10
│ ├── 11
│ ├── ...
├── 2
├── ...
We use a variable curr to denote the current prefix, initialized as 1. At each step, we try to expand or skip prefixes until we find the \k\-th smallest number.
At each step, we calculate how many valid numbers (i.e., numbers \le n with prefix curr) exist under this prefix subtree. Let this count be count(curr):
If k \ge count(curr): the target number is not in this subtree. We skip the entire subtree by moving to the next sibling:
$
curr \leftarrow curr + 1,\quad k \leftarrow k - count(curr)
Otherwise: the target is within this subtree. We go one level deeper:
curr \leftarrow curr times 10,\quad k \leftarrow k - 1
At each level, we enlarge the current range by multiplying by 10 and continue descending until we exceed n.
The time complexity is O(log^2 n), as we perform logarithmic operations for counting and traversing the Trie structure. The space complexity is O(1)$ since we only use a few variables to track the current prefix and count.
| Approach | Complexity |
|---|---|
| Approach 1: Lexicographical Order Tree Traversal | Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level. |
| Approach 2: Binary Search with Counting Function | Time Complexity: O(log(n)^2), where binary search narrows down potential candidates. |
| Trie-Based Counting + Greedy Construction | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Lexicographical Order Tree Traversal | O((log n)^2) | O(1) | Best general solution for large n. Efficiently skips entire prefix ranges. |
| Binary Search with Counting Function | O((log n)^2) | O(1) | Useful when reasoning about lexicographical rank or implementing rank-based search. |
K-th Smallest in Lexicographical Order - Leetcode 440 - Python • NeetCodeIO • 21,998 views views
Watch 9 more video solutions →Practice K-th Smallest in Lexicographical Order with our built-in code editor and test cases.
Practice on FleetCode