{x}
blog image

K-th Smallest in Lexicographical Order

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

Solution Explanation for K-th Smallest in Lexicographical Order

This problem asks us to find the k-th lexicographically smallest integer within the range [1, n]. A lexicographical ordering means we compare numbers as strings; for example, 10 comes before 2 in lexicographical order. A brute-force approach of generating all numbers and sorting is inefficient for large n. The optimal solution leverages a clever counting strategy.

Approach

The core idea is to recursively explore the lexicographical tree formed by the integers. We start at 1. For any given prefix (e.g., 1, 10, 12), we can efficiently count how many numbers in the range [1, n] share that prefix. This count helps us determine whether to continue exploring down the current prefix (by multiplying by 10) or to move to the next prefix (by incrementing).

The count(curr) function is the heart of the algorithm. Given a current number curr, it calculates the number of integers in [1, n] that are lexicographically greater than or equal to curr and smaller than curr + 1 (meaning they share the same prefix as curr). It does this by iteratively multiplying curr by 10 and calculating the contribution of numbers with that prefix.

The main loop starts with curr = 1 and k reduced by 1 (because we're using 0-based indexing). It performs the following steps:

  1. Count: It calls count(curr) to determine the number of integers with the current prefix.
  2. Check: It compares k and the count.
    • If k is greater than or equal to the count, it means there are more numbers with prefixes lexicographically greater than or equal to the current curr than k. We move to the next prefix by incrementing curr.
    • Otherwise, it means the k-th smallest number has the current prefix. We move deeper into the prefix by multiplying curr by 10. Simultaneously we decrement k because we've consumed one lexicographic position.
  3. Iteration: The loop continues until k becomes 0, at which point curr holds the k-th smallest number.

Time Complexity Analysis

The count function iterates at most log₁₀(n) times (the number of digits in n). The main loop also iterates at most log₁₀(n) times in the worst case. Therefore, the overall time complexity is O(log₁₀(n)²), which is very efficient.

Space Complexity Analysis

The space complexity is O(1) because the algorithm uses only a constant amount of extra space regardless of the input size. The recursive calls of count are tail-recursive and can be optimized by the compiler, resulting in constant space usage.

Code Examples (Python, Java, C++, Go)

The code examples provided earlier demonstrate the algorithm's implementation in various programming languages. They directly reflect the approach described above. The key is understanding the count function and the logic of how it updates curr and k in the main loop.