Solution: K-th Smallest in Lexicographical Order

Statement

Given two integers, n and k, return the $k^{th}$ smallest number in the range [1, n] when the numbers are sorted lexicographically.

Note: Lexicographical sorting means ordering numbers like words in a dictionary (alphabetical order)—digit by digit from left to right. For example, the numerical order of 1, 5, and 10 is [1, 5, 10], but their lexicographical order is [1, 10, 5].

Constraints:

• $1 \leq$ k $\leq$ n $\leq 10^9$

Solution

This problem aims to find the $k^{th}$ smallest number in the lexicographical (dictionary) order from $1$ to n. Instead of generating and sorting all numbers from $1$ to n, which would be too slow for large n, let’s take a smarter route by imagining these numbers arranged in a trie. Each node represents a number in a trie, and its children are formed by adding more digits to the end. For example, the root has children $1$ to $9$, and node $1$ has children $10$ ...