# K-th Smallest in Lexicographical Order
**Difficulty:** HARD
[External](https://leetcode.com/problems/k-th-smallest-in-lexicographical-order)
Canonical: https://scaleengineer.com/dsa/problems/k-th-smallest-in-lexicographical-order
**Data structures:** Trie
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Hulu](https://scaleengineer.com/companies/hulu)
---
## Problem
Given two integers `n` and `k`, return _the_ `kth` _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 <= 109`

# Approaches
## Brute Force with Sorting
This is a straightforward approach where we generate all integers from 1 to `n`, convert them to their string representations, and then sort these strings lexicographically. The k-th smallest number is simply the element at the (k-1)-th index of the sorted list.
**Time:** `O(N * log(N) * D)`, where `N` is `n` and `D` is the maximum number of digits in a number up to `n` (i.e., `D = log10(n)`). Generating the list takes `O(N * D)`. Sorting `N` strings of average length `D` takes `O(N * log(N) * D)`. Given the constraints, this is too slow. · **Space:** `O(N * D)`. We need to store `N` strings, where `N` is `n` and `D` is the maximum number of digits (i.e., `log10(n)`). For `n = 10^9`, this would require an enormous amount of memory, leading to a Memory Limit Exceeded error.
**Pros:** Very simple to understand and implement.; Correct for small values of n.
**Cons:** Extremely inefficient for large n.; Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) for the given constraints.
### Explanation
This approach, while simple, is not practical for the given constraints. The main bottleneck is the creation and sorting of a list containing up to `10^9` elements. Generating these numbers and storing them as strings would consume gigabytes of memory. Subsequently, sorting this massive list would be computationally prohibitive.

Here is a Java implementation of this approach:
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int findKthNumber(int n, int k) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(String.valueOf(i));
        }
        Collections.sort(list);
        return Integer.parseInt(list.get(k - 1));
    }
}
```
### Algorithm
*   Create a list of strings.
*   Iterate from `i = 1` to `n`. In each iteration, convert `i` to a string and add it to the list.
*   Sort the list of strings. Standard library sort for strings is lexicographical.
*   Retrieve the string at index `k-1`.
*   Convert this string back to an integer and return it.

## Mathematical Approach using Prefix Tree (Trie)
This approach visualizes the numbers from 1 to `n` as being organized in a 10-ary prefix tree (also known as a trie). The lexicographical order corresponds to a pre-order traversal of this tree. Instead of building the tree explicitly, we can simulate this traversal mathematically. We start at number 1 and at each step, we decide whether to move to the next sibling (e.g., from 1 to 2) or to the first child (e.g., from 1 to 10).
**Time:** `O((log10(N))^2)`. The main `while` loop runs at most `O(log N)` times. At each level of the conceptual prefix tree, `curr` can be incremented at most 9 times. The depth of the tree is `log10(N)`. Inside the loop, `calculateSteps` also takes `O(log10(N))` time because `n1` is multiplied by 10 in each of its iterations until it exceeds `N`. This results in a very fast algorithm. · **Space:** `O(1)`. We only use a few variables to keep track of the state (`curr`, `k`, `steps`, etc.), requiring constant extra space regardless of the input size `n`.
**Pros:** Extremely efficient in both time and space.; Correctly handles the large constraints on n.
**Cons:** The logic is non-trivial and can be difficult to come up with.; Requires careful handling of `long` types to prevent integer overflow.
### Explanation
The core idea is to navigate this conceptual prefix tree without actually building it. We start with `curr = 1`. We need to take `k-1` more steps to find our target. At each node `curr`, we calculate the size of the gap to the next sibling `curr+1`. This 'gap' is the total number of nodes in the pre-order traversal that start with the prefix `curr`. Let's call this count `steps`.

If our remaining steps `k` is larger than `steps`, we know the target is not in this subtree. We can skip all `steps` nodes at once, subtract `steps` from `k`, and move our `curr` pointer to the next sibling `curr+1`.

If `k` is smaller than or equal to `steps`, we know the target is inside this subtree. So we 'enter' the subtree. This means we take one step (from `curr` to its first child `curr*10`), so we decrement `k`. Our new `curr` becomes `curr*10`.

We repeat this until `k` becomes 0, which means we have taken exactly the right number of steps to land on our target number.

Here is the Java implementation:
```java
class Solution {
    public int findKthNumber(int n, int k) {
        long curr = 1;
        k--; // We've taken the first number '1', so k-1 steps remain.

        while (k > 0) {
            long steps = calculateSteps(n, curr, curr + 1);
            if (steps <= k) {
                // The target is not in the subtree of curr.
                // Skip the entire subtree.
                k -= steps;
                // Move to the next sibling.
                curr++;
            } else {
                // The target is in the subtree of curr.
                // Move one step down to the child.
                k--;
                curr *= 10;
            }
        }
        return (int) curr;
    }

    // Calculates how many numbers are in the range [n1, n2) lexicographically,
    // that are also less than or equal to n.
    private long calculateSteps(int n, long n1, long n2) {
        long steps = 0;
        while (n1 <= n) {
            steps += Math.min((long)n + 1, n2) - n1;
            // Move to the next level in the prefix tree.
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }
}
```
It's important to use `long` for `curr`, `n1`, `n2`, and `steps` to avoid potential integer overflow, as intermediate calculations can exceed the `int` range.
### Algorithm
*   Initialize `curr = 1` and decrement `k` by 1 (to account for the first number, 1).
*   Loop as long as `k > 0`.
*   Inside the loop, calculate the number of nodes (`steps`) in the conceptual prefix tree that fall between `curr` and `curr + 1`. This is done by summing up nodes at each level of the tree, starting from the level of `curr`.
*   If `steps <= k`, it means the target is outside the current prefix's subtree. We jump over the entire subtree by updating `k -= steps` and move to the next sibling by `curr++`.
*   Otherwise (`steps > k`), the target is inside the current prefix's subtree. We take one step down into the subtree by `k--` and move to the first child by `curr *= 10`.
*   The loop terminates when `k` becomes 0. The final value of `curr` is the answer.

# Solutions
### Java

```java
class Solution {
private
  int n;
public
  int findKthNumber(int n, int k) {
    this.n = n;
    long curr = 1;
    --k;
    while (k > 0) {
      int cnt = count(curr);
      if (k >= cnt) {
        k -= cnt;
        ++curr;
      } else {
        --k;
        curr *= 10;
      }
    }
    return (int)curr;
  }
public
  int count(long curr) {
    long next = curr + 1;
    long cnt = 0;
    while (curr <= n) {
      cnt += Math.min(n - curr + 1, next - curr);
      next *= 10;
      curr *= 10;
    }
    return (int)cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int n;
  int findKthNumber(int n, int k) {
    this->n = n;
    --k;
    long long curr = 1;
    while (k) {
      int cnt = count(curr);
      if (k >= cnt) {
        k -= cnt;
        ++curr;
      } else {
        --k;
        curr *= 10;
      }
    }
    return (int)curr;
  }
  int count(long long curr) {
    long long next = curr + 1;
    int cnt = 0;
    while (curr <= n) {
      cnt += min(n - curr + 1, next - curr);
      next *= 10;
      curr *= 10;
    }
    return cnt;
  }
};

```

### Python

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

```