K-th Smallest in Lexicographical Order Interview Question for Google

# 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].

For example:
- n = 13, k = 2. The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], and the 2nd smallest number is 10.
- n = 1, k = 1. The answer is 1.

## Naive Approach

A straightforward, but inefficient, approach would be to generate all numbers from 1 to `n`, store them in a list, sort the list lexicographically (as strings), and then return the k-th element. However, this approach will likely exceed time limits for larger values of `n`.

## Optimal Approach

A more efficient approach involves a tree-like structure where each node represents a number. The children of a node are formed by appending digits 0-9 to the node's number. We can then traverse this tree in a depth-first manner, counting the number of nodes visited, until we reach the k-th node.

Here's the algorithm:

1.  Initialize `curr` to 1 (the first number).
2.  Decrement `k` by 1 since we are starting at 1.
3.  While `k > 0`:
    *   Calculate the number of steps from `curr` to `curr + 1`. This tells us how many numbers are lexicographically between `curr` and the next number at the same level (e.g., between 1 and 2, or between 10 and 11).
    *   If `k` is less than the number of steps, then the k-th number is in the subtree of `curr`. So, we multiply `curr` by 10 (go to the next level) and decrement `k` by 1.
    *   Otherwise, the k-th number is not in the subtree of `curr`. So, we increment `curr` (move to the next sibling), and decrement `k` by the number of steps.
4.  Return `curr`.

```python
def findKthNumber(n: int, k: int) -> int:
    curr = 1
    k -= 1
    while k > 0:
        steps = count_steps(n, curr, curr + 1)
        if k >= steps:
            curr += 1
            k -= steps
        else:
            curr *= 10
            k -= 1
    return curr

def count_steps(n: int, n1: int, n2: int) -> int:
    steps = 0
    while n1 <= n:
        steps += min(n + 1, n2) - n1
        n1 *= 10
        n2 *= 10
    return steps

Example

Let's consider the example n = 13, k = 2.

curr = 1, k = 1
steps = count_steps(13, 1, 2). This function calculates the numbers between 1 and 2 (exclusive of 2) in lexicographical order up to 13. These are 1, 10, 11, 12, 13, so there are 5 steps. The function would return 5.
Since k < steps (1 < 5), we have curr = 1 * 10 = 10, and k = 1 - 1 = 0.
The loop terminates, and we return curr = 10.

Big(O) Run-time Analysis

The count_steps function takes O(log n) time because in each iteration, we multiply n1 and n2 by 10, effectively reducing the range by a factor of 10. The findKthNumber function calls count_steps at most k times. In the worst case, k can be close to n. However, in each iteration either curr is incremented or multiplied by 10, and the while loop runs until k is exhausted. The time complexity is approximately O(log n * log n), where the first log n comes from calculating steps, and the second log n comes from the number of iterations to reach k.

Big(O) Space Usage Analysis

The space complexity is O(1) because we are only using a few integer variables (curr, k, steps), and no extra data structures whose size depends on the input are used.

Edge Cases

k = 1: The first number should always be 1.
k = n: The Kth number will be close to n but needs proper calculation.
n is a single digit: The algorithm should still work correctly.
Large n and k: The algorithm efficiently avoids generating all numbers, so it should handle large inputs well, constrained only by the integer limits.