440. K-th Smallest in Lexicographical Order - Explanation

Problem Link

Description

You are given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Example 1:

Input: n = 10, k = 3

Output: 2

Explanation: The lexicographical order is [1,10,2,3,4,5,6,7,8,9]. The third smallest number is 2.

Example 2:

Input: n = 11, k = 3

Output: 2

Explanation: The lexicographical order is [1,10,11,2,3,4,5,6,7,8,9]. The third smallest number is 11.

Constraints:

• 1 <= k <= n <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The simplest approach converts all numbers from 1 to n into strings and sorts them lexicographically. In lexicographical order, "10" comes before "2" because '1' < '2'. After sorting, we simply return the k-th element. This is straightforward but inefficient for large n.

Algorithm

1. Generate all numbers from 1 to n as strings.
2. Sort the list of strings lexicographically.
3. Return the k-th string converted back to an integer.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        nums = []
        for num in range(1, n + 1):
            nums.append(str(num))

        nums.sort()
        return int(nums[k - 1])

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

2. Prefix Count

Intuition

Numbers in lexicographical order form a tree structure where each prefix leads to its extensions. For example, prefix "1" leads to "10", "11", ..., "19", "100", etc. We can count how many numbers exist under any prefix without enumerating them. Starting at "1", we count how many numbers lie in the subtree rooted at the current prefix. If this count is less than or equal to the remaining k, we skip this entire subtree and move to the next sibling. Otherwise, we descend into the subtree by appending a digit.

Algorithm

1. Define count(cur) to calculate how many numbers in [1, n] have cur as a prefix.
2. Start with cur = 1 and i = 1 (position in lexicographical order).
3. While i < k:
   • Calculate steps = count(cur).
   • If i + steps <= k, move to the next sibling: cur++ and i += steps.
   • Otherwise, descend into children: cur *= 10 and i++.
4. Return cur when i == k.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        cur = 1
        i = 1

        def count(cur):
            res = 0
            nei = cur + 1
            while cur <= n:
                res += min(nei, n + 1) - cur
                cur *= 10
                nei *= 10
            return res

        while i < k:
            steps = count(cur)
            if i + steps <= k:
                cur = cur + 1
                i += steps
            else:
                cur *= 10
                i += 1

        return cur

Time & Space Complexity

• Time complexity: $O((\log n) ^ 2)$
• Space complexity: $O(1)$

---

Common Pitfalls

Confusing Lexicographical Order with Numerical Order

In lexicographical order, "10" comes before "2" because strings are compared character by character. Treating numbers numerically instead of as strings leads to completely wrong results. The sequence starts 1, 10, 100, ..., 2, 20, ....

Integer Overflow in Prefix Counting

When counting numbers under a prefix, the prefix and its neighbor are multiplied by 10 repeatedly. For large n, these values can exceed 32-bit integer limits. Use 64-bit integers (long in Java, long long in C++) for the counting logic.

Incorrect Step Counting Logic

The count function must include the prefix itself plus all its extensions up to n. The formula min(neighbor, n + 1) - cur counts numbers in the current level. A common error is using n instead of n + 1, which excludes the boundary value.

Off-by-One in Position Tracking

The position variable i starts at 1 (representing we are at number 1). When moving to a child, increment i by 1. When skipping a subtree, increment i by the step count. Confusing these increments places you at the wrong number.

Not Handling Single-Digit to Multi-Digit Transitions

When descending from prefix "1" to "10", you multiply by 10. But if 10 > n, you cannot descend further. The algorithm must handle cases where the current prefix exceeds n after multiplication, which the count function naturally handles by returning 0.