K-th Smallest in Lexicographical Order
HardPrompt
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 <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward approach where we generate all integers from 1 to n, convert them to their string representations, and then sort these strings lexicographically. The k-th smallest number is simply the element at the (k-1)-th index of the sorted list.
Algorithm
- Create a list of strings.
- Iterate from
i = 1ton. In each iteration, convertito a string and add it to the list. - Sort the list of strings. Standard library sort for strings is lexicographical.
- Retrieve the string at index
k-1. - Convert this string back to an integer and return it.
Walkthrough
This approach, while simple, is not practical for the given constraints. The main bottleneck is the creation and sorting of a list containing up to 10^9 elements. Generating these numbers and storing them as strings would consume gigabytes of memory. Subsequently, sorting this massive list would be computationally prohibitive.
Here is a Java implementation of this approach:
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int findKthNumber(int n, int k) { List<String> list = new ArrayList<>(); for (int i = 1; i <= n; i++) { list.add(String.valueOf(i)); } Collections.sort(list); return Integer.parseInt(list.get(k - 1)); }}Complexity
Time
`O(N * log(N) * D)`, where `N` is `n` and `D` is the maximum number of digits in a number up to `n` (i.e., `D = log10(n)`). Generating the list takes `O(N * D)`. Sorting `N` strings of average length `D` takes `O(N * log(N) * D)`. Given the constraints, this is too slow.
Space
`O(N * D)`. We need to store `N` strings, where `N` is `n` and `D` is the maximum number of digits (i.e., `log10(n)`). For `n = 10^9`, this would require an enormous amount of memory, leading to a Memory Limit Exceeded error.
Trade-offs
Pros
Very simple to understand and implement.
Correct for small values of n.
Cons
Extremely inefficient for large n.
Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) for the given constraints.
This approach visualizes the numbers from 1 to n as being organized in a 10-ary prefix tree (also known as a trie). The lexicographical order corresponds to a pre-order traversal of this tree. Instead of building the tree explicitly, we can simulate this traversal mathematically. We start at number 1 and at each step, we decide whether to move to the next sibling (e.g., from 1 to 2) or to the first child (e.g., from 1 to 10).
Algorithm
- Initialize
curr = 1and decrementkby 1 (to account for the first number, 1). - Loop as long as
k > 0. - Inside the loop, calculate the number of nodes (
steps) in the conceptual prefix tree that fall betweencurrandcurr + 1. This is done by summing up nodes at each level of the tree, starting from the level ofcurr. - If
steps <= k, it means the target is outside the current prefix's subtree. We jump over the entire subtree by updatingk -= stepsand move to the next sibling bycurr++. - Otherwise (
steps > k), the target is inside the current prefix's subtree. We take one step down into the subtree byk--and move to the first child bycurr *= 10. - The loop terminates when
kbecomes 0. The final value ofcurris the answer.
Walkthrough
The core idea is to navigate this conceptual prefix tree without actually building it. We start with curr = 1. We need to take k-1 more steps to find our target. At each node curr, we calculate the size of the gap to the next sibling curr+1. This 'gap' is the total number of nodes in the pre-order traversal that start with the prefix curr. Let's call this count steps.
If our remaining steps k is larger than steps, we know the target is not in this subtree. We can skip all steps nodes at once, subtract steps from k, and move our curr pointer to the next sibling curr+1.
If k is smaller than or equal to steps, we know the target is inside this subtree. So we 'enter' the subtree. This means we take one step (from curr to its first child curr*10), so we decrement k. Our new curr becomes curr*10.
We repeat this until k becomes 0, which means we have taken exactly the right number of steps to land on our target number.
Here is the Java implementation:
class Solution { public int findKthNumber(int n, int k) { long curr = 1; k--; // We've taken the first number '1', so k-1 steps remain. while (k > 0) { long steps = calculateSteps(n, curr, curr + 1); if (steps <= k) { // The target is not in the subtree of curr. // Skip the entire subtree. k -= steps; // Move to the next sibling. curr++; } else { // The target is in the subtree of curr. // Move one step down to the child. k--; curr *= 10; } } return (int) curr; } // Calculates how many numbers are in the range [n1, n2) lexicographically, // that are also less than or equal to n. private long calculateSteps(int n, long n1, long n2) { long steps = 0; while (n1 <= n) { steps += Math.min((long)n + 1, n2) - n1; // Move to the next level in the prefix tree. n1 *= 10; n2 *= 10; } return steps; }}It's important to use long for curr, n1, n2, and steps to avoid potential integer overflow, as intermediate calculations can exceed the int range.
Complexity
Time
`O((log10(N))^2)`. The main `while` loop runs at most `O(log N)` times. At each level of the conceptual prefix tree, `curr` can be incremented at most 9 times. The depth of the tree is `log10(N)`. Inside the loop, `calculateSteps` also takes `O(log10(N))` time because `n1` is multiplied by 10 in each of its iterations until it exceeds `N`. This results in a very fast algorithm.
Space
`O(1)`. We only use a few variables to keep track of the state (`curr`, `k`, `steps`, etc.), requiring constant extra space regardless of the input size `n`.
Trade-offs
Pros
Extremely efficient in both time and space.
Correctly handles the large constraints on n.
Cons
The logic is non-trivial and can be difficult to come up with.
Requires careful handling of
longtypes to prevent integer overflow.
Solutions
Solution
class Solution {private int n;public int findKthNumber(int n, int k) { this.n = n; long curr = 1; --k; while (k > 0) { int cnt = count(curr); if (k >= cnt) { k -= cnt; ++curr; } else { --k; curr *= 10; } } return (int)curr; }public int count(long curr) { long next = curr + 1; long cnt = 0; while (curr <= n) { cnt += Math.min(n - curr + 1, next - curr); next *= 10; curr *= 10; } return (int)cnt; }}class Solution {public: int n; int findKthNumber(int n, int k) { this->n = n; --k; long long curr = 1; while (k) { int cnt = count(curr); if (k >= cnt) { k -= cnt; ++curr; } else { --k; curr *= 10; } } return (int)curr; } int count(long long curr) { long long next = curr + 1; int cnt = 0; while (curr <= n) { cnt += min(n - curr + 1, next - curr); next *= 10; curr *= 10; } return cnt; }};class Solution: def findKthNumber(self, n: int, k: int) -> int: def count(curr): next, cnt = curr + 1, 0 while curr <= n: cnt += min(n - curr + 1, next - curr) next, curr = next * 10, curr * 10 return cnt curr = 1 k -= 1 while k: cnt = count(curr) if k >= cnt: k -= cnt curr += 1 else: k -= 1 curr *= 10 return currVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.