K-th Smallest in Lexicographical Order solution and explanation
Google
9 more videos on this problem
K-th Smallest in Lexicographical Order - Leetcode 440 - PythonNeetCodeIO · 19:06 · 22K views
K-th Smallest in Lexicographical Order | Super Detailed | Dry Run | Leetcode 440 | codestorywithMIKcodestorywithMIK · 42:59 · 21K views
LeetCode 440. Kth Smallest in Lexicographical Order Explanation and Solutionhappygirlzt · 10:48 · 6K views
K-th Smallest in Lexicographical OrderTechdose · 20:29 · 3K views
K-TH SMALLEST IN LEXICOGRAPHIC ORDER | LEETCODE 440 | PYTHON TREE SOLUTIONCracking FAANG · 19:11 · 1K views
440. K-th Smallest in Lexicographical Order LeetcodeCode Crusaders · 3:14 · 986 views
440. K-th Smallest in Lexicographical Order (Leetcode Hard)Programming Live with Larry · 46:33 · 763 views
440. K-th Smallest in Lexicographical Order | Leetcode Daily - PythonLeetcode Daily · 6:06 · 528 views
LeetCode 440 - Kth Smallest in Lexicographical Order - JavaAlpha-Code · 13:48 · 328 views
LeetCode 440 - Kth Smallest in Lexicographical Order - JavaAlpha-Code · 21:14 · 303 views
The problem
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
Approach overview
Problem 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.
Approach 1: Approach 1: Lexicographical Order Tree Traversal
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.
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
# Example usage
sol = Solution()
print(sol.findKthNumber(13, 2)) # Output: 10class Solution {
public int findKthNumber(int n, int k) {
int curr = 1;
k--;
while (k > 0) {
long steps = countSteps(n, curr, curr + 1);
if (steps <= k) {
curr++;
k -= steps;
} else {
curr *= 10;
k--;
}
}
return curr;
}
private long countSteps(long n, long curr, long next) {
long steps = 0;
while (curr <= n) {
steps += Math.min(n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.findKthNumber(13, 2)); // Output: 10
}
}#include <iostream>
using namespace std;
long count_steps(long n, long curr, long next) {
long steps = 0;
while (curr <= n) {
steps += min(n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}
int findKthNumber(int n, int k) {
int curr = 1;
k--;
while (k) {
long steps = count_steps(n, curr, curr + 1);
if (steps <= k) {
curr++;
k -= steps;
} else {
curr *= 10;
k--;
}
}
return curr;
}
int main() {
int n = 13, k = 2;
cout << findKthNumber(n, k) << endl; // Output: 10
return 0;
}function findKthNumber(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++;
k -= steps;
} else {
curr *= 10;
k--;
}
}
return curr;
}
// Example usage
console.log(findKthNumber(13, 2)); // Output: 10#include <stdio.h>
long count_steps(long n, long curr, long next) {
long steps = 0;
while (curr <= n) {
steps += (next > n + 1) ? n + 1 - curr : next - curr;
curr *= 10;
next *= 10;
}
return steps;
}
int findKthNumber(int n, int k) {
int curr = 1;
k--;
while (k > 0) {
long steps = count_steps(n, curr, curr + 1);
if (steps <= k) {
curr++;
k -= steps;
} else {
curr *= 10;
k--;
}
}
return curr;
}
int main() {
int n = 13, k = 2;
printf("%d\n", findKthNumber(n, k)); // Output: 10
return 0;
}using System;
class Solution {
public int FindKthNumber(int n, int k) {
int curr = 1;
k--;
while (k > 0) {
long steps = CountSteps(n, curr, curr + 1);
if (steps <= k) {
curr++;
k -= (int)steps;
} else {
curr *= 10;
k--;
}
}
return curr;
}
private long CountSteps(long n, long curr, long next) {
long steps = 0;
while (curr <= n) {
steps += Math.Min(n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.FindKthNumber(13, 2)); // Output: 10
}
}The Python solution utilizes a helper function count_steps to evaluate numbers between nodes. The main loop in findKthNumber decides whether to go deeper in the tree or move laterally based on the available steps count to reach the k-th number efficiently.
Time Complexity: O(log(n)^2), due to calculation of steps across tree levels.
Space Complexity: O(1), because no additional data structures are involved in the logic.
Approach 2: Approach 2: Binary Search with Counting Function
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.
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
def count_below(n, prefix):
count = 0
factor = 1
while prefix <= n:
count += min(factor, n - prefix + 1)
prefix *= 10
factor *= 10
return count
low, high = 1, n
while low < high:
mid = low + (high - low) // 2
if count_below(n, mid) < k:
low = mid + 1
else:
high = mid
return low
# Example usage
sol = Solution()
print(sol.findKthNumber(13, 2)) # Output: 10class Solution {
public int findKthNumber(int n, int k) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
if (countBelow(n, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private long countBelow(long n, long prefix) {
long count = 0, factor = 1;
while (prefix <= n) {
count += Math.min(factor, n - prefix + 1);
prefix *= 10;
factor *= 10;
}
return count;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.findKthNumber(13, 2)); // Output: 10
}
}#include <iostream>
using namespace std;
long count_below(long n, long prefix) {
long count = 0, factor = 1;
while (prefix <= n) {
count += min(factor, n - prefix + 1);
prefix *= 10;
factor *= 10;
}
return count;
}
int findKthNumber(int n, int k) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
long count = count_below(n, mid);
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int main() {
int n = 13, k = 2;
cout << findKthNumber(n, k) << endl; // Output: 10
return 0;
}function findKthNumber(n, k) {
function countBelow(n, prefix) {
let count = 0, factor = 1;
while (prefix <= n) {
count += Math.min(factor, n - prefix + 1);
prefix *= 10;
factor *= 10;
}
return count;
}
let low = 1, high = n;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (countBelow(n, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Example usage
console.log(findKthNumber(13, 2)); // Output: 10#include <stdio.h>
long count_below(long n, long prefix) {
long count = 0, factor = 1;
while (prefix <= n) {
count += (n - prefix + 1 < factor) ? n - prefix + 1 : factor;
prefix *= 10;
factor *= 10;
}
return count;
}
int findKthNumber(int n, int k) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
long count = count_below(n, mid);
if (count < k)
low = mid + 1;
else
high = mid;
}
return low;
}
int main() {
int n = 13, k = 2;
printf("%d\n", findKthNumber(n, k)); // Output: 10
return 0;
}using System;
class Solution {
public int FindKthNumber(int n, int k) {
int low = 1, high = n;
while (low < high) {
int mid = low + (high - low) / 2;
if (CountBelow(n, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private long CountBelow(long n, long prefix) {
long count = 0;
long factor = 1;
while (prefix <= n) {
count += Math.Min(factor, n - prefix + 1);
prefix *= 10;
factor *= 10;
}
return count;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.FindKthNumber(13, 2)); // Output: 10
}
}The Python binary search solution pushes boundaries to find the k-th smallest number based on counts derived from count_below. Each midpoint estimation ensures efficiency by filtering the search space based on valid number counts within lexicographical order limits.
Time Complexity: O(log(n)^2), guided by binary search over lexicographically summarized regions.
Space Complexity: O(1), operations are handled via primitive variables.
Approach 3: Trie-Based Counting + Greedy Construction
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):
- Each node represents a numeric prefix, starting from an empty root;
- Each node has 10 children, corresponding to appending digits
0 \sim 9; - For example, prefix
1has children10, 11, ldots, 19, and node10has children100, 101, ldots, 109; - This tree naturally reflects lexicographical order traversal.
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.
function findKthNumber(n: number, k: number): number {
function count(curr: number): number {
let next = curr + 1;
let cnt = 0;
while (curr <= n) {
cnt += Math.min(n - curr + 1, next - curr);
curr *= 10;
next *= 10;
}
return cnt;
}
let curr = 1;
k--;
while (k > 0) {
const cnt = count(curr);
if (k >= cnt) {
k -= cnt;
curr += 1;
} else {
k -= 1;
curr *= 10;
}
}
return curr;
}func findKthNumber(n int, k int) int {
count := func(curr int) int {
next := curr + 1
cnt := 0
for curr <= n {
cnt += min(n-curr+1, next-curr)
next *= 10
curr *= 10
}
return cnt
}
curr := 1
k--
for k > 0 {
cnt := count(curr)
if k >= cnt {
k -= cnt
curr++
} else {
k--
curr *= 10
}
}
return curr
}impl Solution {
pub fn find_kth_number(n: i32, k: i32) -> i32 {
fn count(mut curr: i64, n: i32) -> i32 {
let mut next = curr + 1;
let mut total = 0;
let n = n as i64;
while curr <= n {
total += std::cmp::min(n - curr + 1, next - curr);
curr *= 10;
next *= 10;
}
total as i32
}
let mut curr = 1;
let mut k = k - 1;
while k > 0 {
let cnt = count(curr as i64, n);
if k >= cnt {
k -= cnt;
curr += 1;
} else {
k -= 1;
curr *= 10;
}
}
curr
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Lexicographical Order Tree Traversal | Time Complexity: O(log(n)^2), due to calculation of steps across tree levels. |
| Approach 2: Binary Search with Counting Function | Time Complexity: O(log(n)^2), guided by binary search over lexicographically summarized regions. |
| Trie-Based Counting + Greedy Construction | – |
Complexity analysis
| 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. |
Frequently asked questions
Is K-th Smallest in Lexicographical Order easy or hard?
LeetCode classifies this problem as Hard because the optimal solution requires recognizing the implicit lexicographical tree and implementing prefix counting correctly. The algorithm itself is short but the insight behind skipping entire numeric ranges makes it challenging.
K-th Smallest in Lexicographical Order Python/Java solution
Implementations in Python or Java typically use a helper function that counts how many numbers exist between two prefixes (for example between 1 and 2, then 10 and 20, etc.). The algorithm repeatedly moves to the next prefix or deeper into the tree until the k-th number is reached.
How to solve K-th Smallest in Lexicographical Order in O(n)?
A naive solution could generate all numbers from 1 to n, convert them to strings, sort them lexicographically, and pick the k-th element. That approach costs O(n log n) time and O(n) space. Efficient solutions avoid full generation and instead traverse the implicit prefix tree in about O((log n)^2) time.
What is the best approach for K-th Smallest in Lexicographical Order?
The most efficient approach treats numbers from 1 to n as a lexicographical prefix tree and performs a controlled traversal. At each prefix, a counting function determines how many numbers exist under that prefix so entire subtrees can be skipped. This avoids generating all numbers and runs in about O((log n)^2) time with constant space.
Is K-th Smallest in Lexicographical Order asked at Google/Amazon/Meta?
This problem style appears in interviews at large tech companies because it tests prefix reasoning, number ranges, and tree-like traversal without building a full data structure. Variants involving lexicographical ranking or prefix counting have appeared in interviews at Google and Amazon.
What data structure is used in K-th Smallest in Lexicographical Order?
The solution conceptually uses a trie-like prefix tree where each node represents a numeric prefix. The tree is not built explicitly; instead, prefix ranges are counted mathematically to simulate traversal of this structure.
What is the time complexity of K-th Smallest in Lexicographical Order?
The optimal solution runs in O((log n)^2) time and O(1) space. Each step computes how many numbers lie between two lexicographical prefixes, which costs O(log n), and this counting is performed across roughly log n traversal steps.