K-th Smallest in Lexicographical Order

K-th Smallest in Lexicographical Order

1. What is this problem about?

The K-th Smallest in Lexicographical Order interview question asks you to find the $k^{th}$ number in the sequence $1, 2, \dots, n$ when sorted alphabetically ("1", "10", "11", "12", "2", ...). Because $n$ can be up to $10^9$, you cannot actually sort or even list the numbers.

2. Why is this asked in interviews?

Companies like Amazon, Microsoft, and Google use this to test a candidate's ability to traverse a Trie structure conceptually. Even though the Trie isn't explicitly built, the numbers form a 10-ary tree (where 1 is parent of 10-19, etc.). It evaluation your ability to count nodes in subtrees to skip entire branches. It’s a brilliant Trie interview pattern.

3. Algorithmic pattern used

This problem is solved using a Pre-order Traversal on a 10-ary Tree.

1. Count Nodes: Write a helper function countNodes(prefix, n) that calculates how many numbers in range $[1, n]$ start with prefix.
2. Traversal:
   • Start at curr = 1.
   • If the count of numbers in the subtree of curr is $\leq k$, then the $k^{th}$ number is not in this subtree. Move to the sibling: curr = curr + 1, and k = k - count.
   • If the count is $> k$, the $k^{th}$ number is in this subtree. Move down to the first child: curr = curr * 10, and k = k - 1.
3. Repeat: Continue until k == 0.

4. Example explanation

$n = 13, k = 2$

1. Start at curr = 1.
2. countNodes(1, 13): Numbers are {1, 10, 11, 12, 13}. Count = 5.
3. Since $k=2$ and $5 \geq 2$, the target is in the subtree of 1.
4. Move down: curr = 1 * 10 = 10. k = 2 - 1 = 1.
5. Next is the $1^{st}$ smallest in subtree of 10, which is 10 itself. Result: 10.

5. Common mistakes candidates make

• String Sorting: Attempting to convert numbers to strings and sort them ($O(N \log N)$), which crashes for $N=10^9$.
• Incorrect node counting: Failing to account for the boundary $n$ when calculating how many numbers start with a given prefix.
• Off-by-one: Mistakes in decreasing $k$ when moving down or across the tree.

6. Interview preparation tip

Visualize the number system as a tree. Lexicographical order is exactly the same as a Pre-order DFS traversal. Learning to count subtree sizes without visiting every node is a powerful optimization for many Design interview patterns.