K-th Smallest in Lexicographical Order
Hard · Tries · Trie · Math
Problem
You are given two integers n and k. Write the integers 1 through n as strings and sort them in dictionary (lexicographical) order. Return the k-th number in that order (counting from 1).
For example, with n = 12 the order is 1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9.
n can be as large as 10^9, so the numbers cannot be listed. Picture them as a prefix tree with ten children per node: 1 has children 10…19, 10 has children 100…109, and so on. Dictionary order is a preorder walk of that tree.
Examples
Input: n = 15, k = 4 Output: 12
The order starts 1, 10, 11, 12, 13, 14, 15, 2, …, so the fourth number is 12.
Input: n = 5, k = 5 Output: 5
With one-digit numbers, dictionary order and numeric order agree.
Input: n = 100, k = 3 Output: 100
The order begins 1, 10, 100: each step goes one level deeper.
Constraints
- 1 <= k <= n <= 10^9
Approaches
- Walk the dictionary order one number at a time — time O(k · log n), space O(1)
Follow-up
The same subtree count answers "how many numbers up to n start with a given prefix" in O(log n). How would you find the position (rank) of a given number x in the dictionary order instead?
Related problems
Start free on Cariara · Coding problems · System design studio
