K-th Smallest in Lexicographical Order - Video Solutions

Problem Overview: Given integers n and k, return the k-th smallest number in lexicographical order within the range [1, n]. Instead of sorting numbers as strings (which would be expensive), you navigate the implicit dictionary order of numbers like a prefix tree.

Approach 1: Lexicographical Order Tree Traversal (O((log n)^2) time, O(1) space)

Numbers from 1 to n can be visualized as a prefix tree (similar to a trie) where each node represents a numeric prefix. For example, prefix 1 expands to 10, 11, 12.... Instead of generating all numbers, count how many values exist under a prefix using a helper function that measures the gap between two lexicographical prefixes.

Start at prefix 1. At each step, compute how many numbers lie under the current prefix. If the count is less than or equal to k, skip the entire subtree and move to the next prefix (like 1 → 2). Otherwise, go deeper into the tree (1 → 10). This approach simulates a preorder traversal of the lexicographical tree without building it explicitly. Because each prefix expansion and counting step takes about O(log n) time and you move through roughly log n levels, the overall complexity becomes O((log n)^2).

This technique is efficient even for very large n (up to 10^9) because it skips entire subtrees rather than enumerating numbers. Conceptually it combines ideas from trie traversal and prefix counting.

Approach 2: Binary Search with Counting Function (O((log n)^2) time, O(1) space)

Another strategy treats the lexicographical order as a searchable space and applies binary search. For a candidate number, compute how many numbers from 1..n appear before it in lexicographical order. This counting relies on the same prefix-range calculation used in the tree traversal approach.

Binary search repeatedly narrows the range until the number whose lexicographical rank equals k is found. Each rank computation walks through digit levels and counts valid prefixes, which costs O(log n). With O(log n) binary search iterations, the final complexity remains O((log n)^2).

The method is conceptually clean if you're comfortable with ranking functions, though the traversal approach usually results in simpler code.

Recommended for interviews: The lexicographical prefix traversal is the solution most interviewers expect. It demonstrates that you recognize the implicit 1..n lexicographical structure and can efficiently skip entire branches using prefix counts. A brute-force string sort would be O(n log n) and impractical for large inputs, while the prefix traversal shows strong algorithmic insight.