440. K-th Smallest in Lexicographical Order - Detailed Explanation

Problem Statement

Given two integers, n and k, your task is to find the k-th smallest number in the lexicographical order of all integers in the range [1, n].

Lexicographical order means that the numbers are sorted as if they were strings. For example, "10" comes before "2" when compared lexicographically.

Example 1

Input: n = 13, k = 2
Lexicographical Order: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
Output: 10
Explanation: The 2nd number in the sorted order is 10.

Example 2

Input: n = 1, k = 1
Lexicographical Order: [1]
Output: 1
Explanation: With only one number available, the first (and only) number is 1.

Example 3

Input: n = 100, k = 10
Lexicographical Order (first few numbers): [1, 10, 100, 11, 12, 13, 14, 15, 16, 17, ...]
Output: 17
Explanation: Counting through the lexicographical order, the 10th number is 17.

Constraints:

1 ≤ k ≤ n ≤ 10^9
The solution must work efficiently given the large possible value of n.

Hints to Guide Your Approach

Think Tree Structure:
Imagine all numbers from 1 to n arranged in a prefix tree (trie) where each node represents a prefix. Traversing this tree in pre-order gives the lexicographical order.
Count the Nodes:
Instead of generating every number, you can count the numbers under each prefix. This allows you to skip whole subtrees if the k-th element isn’t within them.
Skip Subtrees:
If you know that the count of numbers starting with a given prefix is less than k, you can subtract that count from k and move to the next prefix.

Approaches

Approach 1: Brute Force (Generate and Sort)

Idea:
Generate all numbers from 1 to n, convert them to strings, sort them lexicographically, and then pick the k-th element.
Steps:
1. Generate a list of numbers from 1 to n.
2. Convert each number to a string.
3. Sort the list based on string order.
4. Convert the k-th string back to an integer.
Why It Falls Short:
While this approach is easy to implement, it has a time complexity of O(n log n) due to sorting and can use too much memory when n is very large (up to 10^9). This makes it impractical for large inputs.

Approach 2: Optimal Prefix Counting Method

Idea:
Use a counting method that leverages the structure of lexicographical order. Think of the numbers as nodes in a tree where each node (prefix) has children (extended numbers). By counting how many numbers fall under each prefix, you can decide to “skip” entire sections.
Steps:
1. Start with prefix = 1.
  This represents the first number in lexicographical order.
2. Count the nodes (numbers) under the current prefix:
  Define a helper function count(prefix, n) that counts how many numbers starting with the given prefix are within the range [1, n].
3. Decide whether to go deeper or move to the next prefix:
  - If the count is less than k, then the k-th number is not in this subtree. Subtract the count from k and move to the next sibling (i.e., prefix + 1).
  - If the count is greater than or equal to k, then the k-th number lies in this subtree. Append a digit (i.e., multiply the prefix by 10) to dive into the next level.
4. Repeat until k becomes 0.
  The current prefix is your answer.
Benefits:
This method only requires traversing through the tree structure based on digit counts and skips large parts of the search space, leading to an efficient solution with a complexity roughly proportional to O(log n).

Detailed Explanation and Pseudocode

Prefix Counting Helper Function

The helper function calculates how many numbers under a given prefix are ≤ n. Here’s the idea:

Initialize curr with the prefix and next with prefix + 1.
While curr ≤ n:
- Add min(n + 1, next) - curr to the count. This gives the count of numbers between curr and next - 1.
- Multiply curr and next by 10 to move to the next level.

Pseudocode:

function count(prefix, n):
    count = 0
    curr = prefix
    next = prefix + 1
    while curr <= n:
        count += min(n + 1, next) - curr
        curr *= 10
        next *= 10
    return count

Main Logic

set current = 1
decrement k by 1 (since we start from prefix 1)
while k > 0:
    count = count(current, n)
    if count <= k:
        k -= count
        current += 1      // move to next sibling prefix
    else:
        k -= 1
        current *= 10     // move down to the first child in the prefix tree
return current

This loop gradually refines the prefix until k becomes 0, meaning the current prefix is the k-th smallest number.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Explanation:

The count function calculates how many numbers with the given prefix exist in the range [1, n].
In findKthNumber, we adjust k (subtracting 1 initially) and then either skip a whole prefix subtree or move deeper into the tree until we find the k-th number.

Complexity Analysis

Time Complexity:
The while loop in the optimal approach runs roughly proportional to the number of digits in n (i.e., O(log n)). In each iteration, the helper function may traverse a few levels, but overall the time complexity is efficient.
Space Complexity:
O(1) – Only a constant amount of extra space is used regardless of the size of n.

Common Mistakes

Off-by-One Errors:
Not adjusting k properly (remember to decrement k by 1 at the start because the counting includes the current prefix).
Incorrect Count Calculation:
Failing to correctly calculate the number of numbers under a given prefix can lead to skipping too many or too few nodes.
Integer Overflow:
In Java, using int for calculations in the counting function can overflow; hence, use long for intermediate counts.

Edge Cases

n = 1:
The only number is 1, so the answer should be 1 regardless of k.
k = 1:
The first number in lexicographical order is always 1.
Large n:
The algorithm is designed to handle large values of n efficiently by skipping entire subtrees.

Variations:
- Find the k-th largest in lexicographical order.
- Return the entire lexicographical order for a given n.
Related Problems for Further Practice:
- Lexicographical Numbers: Explore problems that involve lexicographical ordering.
- Trie-Based Problems: Practice problems that require working with prefix trees.
- Binary Search Problems: Problems that require skipping or counting ranges (e.g., finding the k-th missing number).