MANG Problem #14: K-th Smallest in Lexicographical Order (Hard)

1. Problem Statement

Given two integers n and k, return the k-th lexicographically smallest integer in the range [1, n].

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 is 10.

2. Approach: Denary Tree Traversal

Instead of sorting (which is too slow), we treat the numbers as nodes in a 10-ary tree (Denary Tree).

Root 1 has children 10, 11, 12... 19.
Root 10 has children 100, 101...

Count Nodes: For a current prefix, calculate how many numbers exist in the range [1, n] that start with that prefix.
Navigate:
- If count <= k: The target is inside this subtree. Move to the first child (prefix * 10) and decrement k by 1.
- If count > k: The target is outside this subtree. Move to the next sibling (prefix + 1) and subtract count from k.

3. Java Implementation

public int findKthNumber(int n, int k) {
    int curr = 1;
    k = k - 1; // We start at the first number (1)
    
    while (k > 0) {
        long steps = countSteps(n, curr, curr + 1);
        if (steps <= k) {
            curr += 1; // Move to sibling
            k -= steps;
        } else {
            curr *= 10; // Move to child
            k -= 1;
        }
    }
    return curr;
}

private long countSteps(int n, long n1, long n2) {
    long steps = 0;
    while (n1 <= n) {
        steps += Math.min(n + 1, n2) - n1;
        n1 *= 10;
        n2 *= 10;
    }
    return steps;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Lexicographical order is just Pre-order Traversal on a 10-ary tree.
The Skipping Logic: The countSteps function is the hero. It tells us: "How many numbers are there between curr and curr + 1?" If that number is less than k, we don't need to visit any of them. We jump over them all in $O(1)$.
Efficiency: By skipping entire subtrees, we achieve $O(\log n \times \log n)$ time, which is incredibly fast for $n = 10^9$.

5. Interview Discussion

Interviewer: "Why use long for n1 and n2?"
You: "Because when we multiply by 10, we could easily exceed Integer.MAX_VALUE before the n1 <= n check."
Interviewer: "What is the tree height?"
You: "The height is $O(\log n)$, which is why this approach is so much better than generating or sorting all numbers."