K-th Smallest in Lexicographical Order

Given two integers n and k, return the k<sup>th</sup> lexicographically smallest integer in the range [1, n].

Example 1:

Input: n = 13, k = 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2:

Input: n = 1, k = 1
Output: 1

Constraints:

• 1 <= k <= n <= 10<sup>9</sup>

# Lexicographical Order of Integers

## Problem Description

Given two integers `n` and `k`, the task is to find the k-th lexicographically smallest integer in the range `[1, n]`. Lexicographical order means ordering numbers as if they were strings.

For example, given `n = 13` and `k = 2`, the lexicographical order is `[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]`, so the second smallest number is `10`.

## Naive Approach

One straightforward approach is to generate all numbers from 1 to n, sort them lexicographically (i.e., convert them to strings and sort), and then return the k-th element. However, this approach has a time complexity of O(n log n) due to the sorting step, and it also requires O(n) space to store the numbers.

## Optimal Approach

A more efficient approach involves constructing the lexicographical order on the fly without storing all the numbers. The key idea is to treat the numbers as nodes in a tree, where each node's children are formed by appending digits from 0 to 9. We can traverse this implicit tree to find the k-th smallest number. The algorithm operates as follows:

1.  Start with the current number `curr = 1` and `k = k - 1` (since we start at 1).
2.  Define a helper function `steps(n, curr, next)` that counts how many numbers are between `curr` and `next` in the lexicographical order.
3.  If the number of steps is less than or equal to `k`, it means the k-th number is not in the subtree rooted at `curr`. So, move to the next sibling by incrementing `curr` and reduce `k` by the number of steps.
4.  If the number of steps is greater than `k`, it means the k-th number is in the subtree rooted at `curr`. So, move to the first child by multiplying `curr` by 10.
5.  Repeat steps 2-4 until `k` becomes 0. Return `curr`.

```python
class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def steps(n, curr, next):
            steps = 0
            while curr <= n:
                steps += min(n + 1, next) - curr
                curr *= 10
                next *= 10
            return steps

        curr = 1
        k -= 1
        while k > 0:
            step = steps(n, curr, curr + 1)
            if step <= k:
                curr += 1
                k -= step
            else:
                curr *= 10
                k -= 1
        return curr

Example

Let's take n = 13 and k = 2.

1. curr = 1, k = 1
2. steps(13, 1, 2) = min(14, 2) - 1 + min(14, 20) - 10 = 1 + 4 = 5
3. Since 5 > 1, curr = 10, k = 0
4. Return 10

Big(O) Run-time Analysis

The time complexity is O(log n + k). The steps function takes O(log n) in the worst case because the while loop multiplies curr and next by 10 in each iteration until curr exceeds n. The outer while loop runs until k becomes 0, so it takes O(k). Thus, the total run-time complexity is O(log n + k). However, since k <= n, in the worst case, this can also be represented as O(n).

Big(O) Space Usage Analysis

The space complexity is O(1) because the algorithm uses only a few constant variables. It does not use any additional data structures that scale with the input size n or k.

Edge Cases

1. n = 1, k = 1: The algorithm should return 1. The provided solution handles this case correctly.
2. k = 1: The algorithm should return 1. The provided solution handles this case correctly.
3. n is very large: The algorithm handles large values of n because it doesn't store all numbers from 1 to n. It calculates the count of numbers dynamically using the steps function.
4. k is close to n: The algorithm handles larger k as well by incrementing curr until the target k is found.