The problem K-th Smallest in Lexicographical Order asks you to find the k-th smallest number in lexicographical (dictionary) order among all the numbers from 1 to n (inclusive).
n (the upper limit) and k (the position in lexicographical order).k-th smallest in this ordering.n = 13, the numbers in lexicographical order are: 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9. If k = 2, the answer is 10.1 <= k <= n <= 10^9
At first glance, you might consider generating all numbers from 1 to n, sorting them as strings, and picking the k-th one. However, this brute-force approach is not feasible for large n (up to 109), as it would be far too slow and memory-intensive.
The key realization is that lexicographical order can be visualized as a traversal of a 10-ary tree (each node has up to 10 children, corresponding to appending digits 0-9). Each number is a node, and its children are numbers formed by appending digits. By counting how many numbers are in each subtree, we can "jump" over entire branches, efficiently navigating to the k-th number without listing all numbers.
This transforms the problem from brute-force enumeration to a clever counting and traversal problem, similar to how you might skip entire sections in a dictionary by knowing how many words start with a given prefix.
We solve the problem by simulating a lexicographical traversal and using counting to skip unnecessary branches. Here’s how:
n.k is large enough.curr = 1 (the smallest number).k > 1:
steps between curr and curr+1 (i.e., all numbers starting with the current prefix).steps < k:
curr + 1 and decrease k by steps.curr *= 10 and decrease k by 1 (for the current node).k == 1, curr is our answer.n by expanding the range at each digit level.min(n+1, next) - curr to the count, where next = curr * 10.This approach efficiently finds the answer without generating or storing all numbers.
Let's use n = 13, k = 2 as an example.
curr = 1, k = 2.steps = 5 >= k, we go deeper: curr = 10, k = 1.k = 1, so the answer is curr = 10.k had been larger, we would have skipped subtrees as needed, always moving to the next prefix or going deeper.
This method generalizes to much larger values of n and k.
O(n \log n) (since you'd need to sort up to n numbers as strings).O(n) to store all numbers.n (up to 109).O(\log n \cdot \log n). Each step involves counting nodes, which takes up to O(\log n) time, and we do this up to O(\log n) times (since the prefix can only grow so much).O(1), since we only use a few variables regardless of n.The optimized approach is efficient and works even for the largest constraints.
The K-th Smallest in Lexicographical Order problem is best solved by leveraging the structure of lexicographical order as a tree, using efficient counting to skip over subtrees. This avoids the inefficiency of brute-force generation and sorting, enabling us to work with very large values of n. The key insight is to count how many numbers exist with a given prefix and use this to jump to the correct position, making the solution both elegant and highly efficient.
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
def count_steps(n, curr, next_):
steps = 0
while curr <= n:
steps += min(n + 1, next_) - curr
curr *= 10
next_ *= 10
return steps
curr = 1
k -= 1
while k > 0:
steps = count_steps(n, curr, curr + 1)
if steps <= k:
curr += 1
k -= steps
else:
curr *= 10
k -= 1
return curr
class Solution {
public:
int findKthNumber(int n, int k) {
auto count_steps = [](long n, long curr, long next) {
int steps = 0;
while (curr <= n) {
steps += min(n + 1L, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
};
long curr = 1;
k--;
while (k > 0) {
int steps = count_steps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
} else {
curr *= 10;
k -= 1;
}
}
return (int)curr;
}
};
class Solution {
public int findKthNumber(int n, int k) {
long curr = 1;
k--;
while (k > 0) {
int steps = countSteps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
} else {
curr *= 10;
k -= 1;
}
}
return (int)curr;
}
private int countSteps(int n, long curr, long next) {
int steps = 0;
while (curr <= n) {
steps += Math.min(n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}
}
var findKthNumber = function(n, k) {
function countSteps(n, curr, next) {
let steps = 0;
while (curr <= n) {
steps += Math.min(n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}
let curr = 1;
k--;
while (k > 0) {
let steps = countSteps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
} else {
curr *= 10;
k -= 1;
}
}
return curr;
};