440. K-th Smallest in Lexicographical Order
Problem Description
Given two numbers n
and k
, the task is to find the kth
smallest number in the range [1, n]
when the numbers are arranged in lexicographic order. Lexicographic order means the numbers are arranged like they would be in a dictionary, and not in numerical order. For example, with n = 13
, the sequence in lexicographic order is 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9
.
Intuition
To solve this problem, a key observation is understanding how numbers are arranged in lexicographic order, particularly focusing on the tree structure that this order implies. Every number can be seen as the root of a sub-tree, with its immediate children being obtained by appending a digit from 0-9
to the number.
For example, for the range [1, 13]
, at the first level of this tree, we have 1
, 2
, ..., 9
. If we look closer at the sub-tree under 1
, the second level would contain 10
, 11
, 12
, 13
. No further numbers can be under 1
because that would exceed the range.
To find the kth
lexicographic number, we can perform a sort of "guided" depth-first search through this tree.
The key insight is to skip over entire sub-trees that we don't need to count. The count
function aids with this, as it counts how many numbers are present in the sub-tree that starts with the prefix curr
. It essentially tells us how many steps we can jump directly without visiting each node. If there are enough steps to skip the current sub-tree and still have some part of k
remaining, we move to the next sibling by adding 1
to curr
. Otherwise, we go to the next depth of the tree by changing curr
to curr * 10
(appending a 0
).
Keep in mind that we subtract one from k
initially because we start counting from 1
(the first number) and each time we either skip a sub-tree or go deeper, we need to decrement k
accordingly until we traverse k
steps.
Learn more about Trie patterns.
Solution Approach
The findKthNumber
method begins the search with the current number set to 1
and decrements k
by 1
since we start from the first number.
The count
function calculates the number of integers under the current prefix within the range up to n
. It achieves this by iterating through the range, counting by moving on to child nodes in the sub-tree. For the given curr
prefix, the loop steps through each level in its sub-tree by appending zeros (multiplying by 10
) to the current prefix and to the next smallest number with the same number of digits (next
). The range from curr
to next - 1
represents a full set of children in lexicographic order under the current prefix.
The min(n - curr + 1, next - curr)
calculation determines how many numbers to count at the current tree level (between the curr
and the next
prefix). It uses the smaller of either the total number in the range or the number up to the next prefix (not inclusive) to avoid going out of bounds of the range [1, n]
.
In the main while loop of findKthNumber
, we repeatedly decide whether to skip the current prefix's sub-tree or go deeper into the sub-tree:
-
If
k >= cnt
(wherecnt
is the count of numbers under the current prefix), it means that thekth
number is not under the current prefix's sub-tree. Therefore, we should skip to the next sibling by incrementingcurr
and decrementingk
bycnt
. -
If
k < cnt
, we go into the current sub-tree by moving to the next level (makingcurr
ten times larger, that is, appending a '0'). Since we are still looking inside this sub-tree, we decrementk
by1
to account for moving one level deeper. Now,k
represents the relative order of the search inside the sub-tree.
We repeat this process until k
becomes 0
, which means we've found our kth
number, represented by the current curr
value.
This algorithm effectively skips large chunks of the search space, rapidly homing in on the kth
smallest number in lexicographic order without having to examine every number individually.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using n = 15
and k = 4
. We want to find the 4th smallest number in the range [1, 15]
when the numbers are arranged in lexicographic order.
-
Begin with the current number set to
1
and decrementk
by1
, as we start from the first number. Now,curr = 1
andk = 3
. -
Calculate the count of numbers under the current prefix using the
count
function. Forcurr = 1
, this count includes1, 10, 11, 12, 13, 14, 15
, which equals 7. Sincek = 3
is less thancnt = 7
, we don't skip the current prefix's sub-tree. -
Move to the next level in this sub-tree by making
curr = 1 * 10 = 10
and decrementk
by1
to account for the first number we currently at (which is1
). Now,curr = 10
andk = 2
. -
Since
k
is still positive, we again compute the count for the currentcurr = 10
. The count includes10
only since11
would go to the next level of this sub-tree. So,cnt = 1
. -
Since
k >= cnt
, we skip the number10
by incrementingcurr
to11
and reducingk
bycnt
(which is1
). Now,curr = 11
andk = 1
. -
Now, with
curr = 11
, we again compute the count. It contains11
only (since12
goes to the next level), socnt = 1
. -
Since
k >= cnt
, we skip the number11
by incrementingcurr
to12
and reducingk
bycnt
. Now,curr = 12
andk = 0
.
Since k
is now 0
, we've reached the 4th smallest number in the lexicographic order, which is 12
.
This is how the solution approach helps in finding the kth smallest number in lexicographic order without having to list out or visit each number, by making use of the tree structure and skipping over the entire sub-trees when possible.
Solution Implementation
1class Solution:
2 def find_kth_number(self, n: int, k: int) -> int:
3 # Helper function to count the number of elements less than or equal to current prefix within n
4 def count_prefix(prefix):
5 next_prefix = prefix + 1
6 total = 0
7 # Keep expanding the current prefix by a factor of 10 (moving to the next level in the trie)
8 while prefix <= n:
9 # Calculate the number of elements between the current prefix and the next prefix
10 total += min(n - prefix + 1, next_prefix - prefix)
11 next_prefix *= 10
12 prefix *= 10
13 return total
14
15 # Starting with the first prefix
16 current = 1
17 # Since we start from 1, we subtract 1 from k to match 0-based indexing
18 k -= 1
19
20 while k:
21 count = count_prefix(current)
22 # If the remaining k is larger than the count,
23 # it means the target is not in the current subtree
24 if k >= count:
25 k -= count # Skip the current subtree
26 current += 1 # Move to the next sibling
27 else:
28 # The target is within the current subtree
29 k -= 1 # Move to the next level in the trie
30 current *= 10
31 # The kth number has been found
32 return current
33
1class Solution {
2 // Class level variable to store the upper limit.
3 private int upperLimit;
4
5 // Method to find k-th smallest number in the range of 1 to n inclusive.
6 public int findKthNumber(int n, int k) {
7 // Assign the upper limit.
8 this.upperLimit = n;
9 // Start with the smallest number 1.
10 long current = 1;
11 // Decrement k as we start with number 1 already considered.
12 k--;
13
14 // Loop until we find the k-th number.
15 while (k > 0) {
16 // Determine the count of numbers prefixed with 'current'.
17 int count = getCount(current);
18 // If k is larger than or equal to the count, skip this prefix.
19 if (k >= count) {
20 k -= count; // Decrement k by the count of numbers.
21 current++; // Move to the next number.
22 } else {
23 // If k is smaller than the count, go deeper into the next level.
24 k--; // We're considering a number (current * 10) in next step, hence decrement k.
25 current *= 10; // Move to the next level by multiplying by 10.
26 }
27 }
28 // The current number is the k-th smallest number.
29 return (int) current;
30 }
31
32 // Helper method to count the numbers prefixed with 'current' within 'n'.
33 public int getCount(long current) {
34 // Find the next sibling in the tree (e.g., from 1 to 2, 10 to 20 etc.).
35 long next = current + 1;
36 // Initialize the count of numbers.
37 long count = 0;
38
39 // Loop until 'current' exceeds 'upperLimit'.
40 while (current <= upperLimit) {
41 // Add the delta between n and current to the count.
42 // We take the minimum of delta and (next - current) to handle cases where
43 // 'n' is less than 'next - 1' (e.g., when 'n' is 12 and range is 10 to 20).
44 count += Math.min(upperLimit - current + 1, next - current);
45
46 // Move both 'current' and 'next' one level down the tree.
47 next *= 10;
48 current *= 10;
49 }
50 // Return the count after casting it to an integer.
51 return (int) count;
52 }
53}
54
1class Solution {
2public:
3 int upperLimit; // This will store the upper limit upto which we need to find the numbers.
4
5 // This method will find the kth smallest integer in the lexicographical order for numbers from 1 to n.
6 int findKthNumber(int n, int k) {
7 upperLimit = n; // Set the upper limit for the numbers
8 --k; // Decrement k as we start from 0 to make calculations easier
9 long long currentPrefix = 1; // We start with 1 as the smallest lexicographical number
10
11 // Keep looking for the kth number until k reaches 0
12 while (k) {
13 int countOfNumbers = getCountOfNumbersWithPrefix(currentPrefix);
14
15 if (k >= countOfNumbers) {
16 // If k is larger than the count, skip the entire subtree
17 k -= countOfNumbers;
18 ++currentPrefix; // Move to the next prefix
19 } else {
20 // If k is within the range, go deeper into the subtree
21 k--; // Decrement k as we have found another smaller number
22 currentPrefix *= 10; // Append a 0 to dive into the next level of the tree
23 }
24 }
25 return static_cast<int>(currentPrefix); // Cast and return the current number
26 }
27
28 // This helper method will count the numbers with a given prefix up to the upper limit.
29 int getCountOfNumbersWithPrefix(long long prefix) {
30 long long nextPrefix = prefix + 1; // Get the next prefix by adding one
31 int count = 0; // Initialize the count for the numbers
32
33 // Calculate the count of the numbers with the current prefix within the bounds of 'n'
34 while (prefix <= upperLimit) {
35 // Add the minimum of the range to the current prefix or the numbers until 'n'
36 count += min(static_cast<long long>(upperLimit) - prefix + 1, nextPrefix - prefix);
37 nextPrefix *= 10; // Move to the next level by appending a 0 to nextPrefix
38 prefix *= 10; // Move to the next level by appending a 0 to prefix
39 }
40 return count; // Return the count of numbers with the current prefix
41 }
42};
43
1let upperLimit: number; // This stores the upper limit up to which numbers are found.
2
3/**
4 * Finds the kth smallest integer in lexicographical order for numbers from 1 to n.
5 * @param {number} n - The upper limit of the number range.
6 * @param {number} k - The position of the number to find.
7 * @returns {number} - The kth smallest lexicographical number.
8 */
9function findKthNumber(n: number, k: number): number {
10 upperLimit = n; // Set the upper limit for the range of numbers.
11 k -= 1; // Decrement k as we start from 0 to simplify calculations.
12 let currentPrefix: number = 1; // Start with 1 as the smallest lexicographical number.
13
14 while (k > 0) {
15 let countOfNumbers: number = getCountOfNumbersWithPrefix(currentPrefix);
16
17 if (k >= countOfNumbers) {
18 // The ith number is beyond the current subtree.
19 k -= countOfNumbers;
20 currentPrefix += 1; // Go to the next sibling prefix.
21 } else {
22 // The ith number is within the current subtree.
23 k -= 1; // We step over a number in lexicographical order.
24 currentPrefix *= 10; // Go down to the next level in the tree.
25 }
26 }
27 return currentPrefix; // Return the found number.
28}
29
30/**
31 * Counts the numbers with a specific prefix within the upper limit.
32 * @param {number} prefix - The current prefix to count within.
33 * @returns {number} - The count of numbers with the specified prefix.
34 */
35function getCountOfNumbersWithPrefix(prefix: number): number {
36 let nextPrefix: number = prefix + 1; // Next prefix sequence.
37 let count: number = 0; // Count of numbers with the given prefix.
38
39 while (prefix <= upperLimit) {
40 // Calculate minimum of the remaining numbers with current prefix vs whole next level.
41 count += Math.min(upperLimit - prefix + 1, nextPrefix - prefix);
42 nextPrefix *= 10; // Prepare the nextPrefix for the next level.
43 prefix *= 10; // Prepare the prefix for the next level.
44 }
45 return count; // Return the count.
46}
47
Time and Space Complexity
The provided code is designed to find the k
-th smallest number in the lexicographical order of numbers from 1
to n
.
Time Complexity
The time complexity of the function depends on two main factors: the number of iterations required to decrement k
to 0
, and the time taken by the count
function, which calculates the number of lexicographic steps from the current prefix to the next.
-
The
count
function has a while loop that runs as long ascurr <= n
. In each iteration, thecurr
is multiplied by10
. This loop could theoretically run up toO(log(n))
times because the maximum "distance" from1
ton
in terms of 10x increments is logarithmic with base10
ton
. -
The outer while loop that decrements
k
runs untilk
becomes0
. However, every time we updatecurr
(either bycurr += 1
orcurr *= 10
), we make a relatively large jump in terms of lexicographical order, especially when we multiply by10
. Despitek
starting with a maximum ofn
, because of the exponential nature of the jumps, the total number of times this loop will iterate is alsoO(log(n))
in practice.
The result is that the overall time complexity is O(log(n)^2)
. Each decrement of k
in the worst case can call count
, and there can be up to O(log(n))
such operations.
Space Complexity
The space complexity of the solution is O(1)
. Outside of count
's recursive calls, no additional memory that scales with n
or k
is used, as we're only maintaining constant space variables like curr
, next
, cnt
, and k
.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!