# LeetCode 440: K-th Smallest in Lexicographical Order

## Problem Restatement

We are given two integers `n` and `k`.

We need to return the `k`-th smallest integer in lexicographical order among all integers from `1` to `n`.

Lexicographical order means dictionary order, as if every number were compared as a string.

For example, when:

```python
n = 13
```

the numbers in lexicographical order are:

```python
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
```

So when:

```python
k = 2
```

the answer is:

```python
10
```

The official problem asks for the `k`-th lexicographically smallest integer in `[1, n]`, with `1 <= k <= n <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integers `n` and `k` |
| Output | The `k`-th number in lexicographical order |
| Range | Numbers from `1` to `n` |
| Constraint | `1 <= k <= n <= 10^9` |

Example function shape:

```python
def findKthNumber(n: int, k: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 13
k = 2
```

Lexicographical order:

```python
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
```

The second number is:

```python
10
```

Example 2:

```python
n = 1
k = 1
```

There is only one number:

```python
[1]
```

Answer:

```python
1
```

Example 3:

```python
n = 100
k = 10
```

The beginning of lexicographical order is:

```python
1, 10, 100, 11, 12, 13, 14, 15, 16, 17
```

So the answer is:

```python
17
```

## First Thought: Generate and Sort

A simple solution is:

1. Generate every number from `1` to `n`.
2. Sort them as strings.
3. Return the `k - 1` index.

Code idea:

```python
nums = list(range(1, n + 1))
nums.sort(key=str)
return nums[k - 1]
```

This is correct for small `n`.

But `n` can be as large as `10^9`, so we cannot generate all numbers.

We need to jump through lexicographical order without listing every integer.

## Key Insight

Lexicographical order is the same as preorder traversal of a prefix tree.

Think of numbers as prefixes.

The root has children:

```text
1, 2, 3, 4, 5, 6, 7, 8, 9
```

Node `1` has children:

```text
10, 11, 12, 13, 14, 15, 16, 17, 18, 19
```

Node `10` has children:

```text
100, 101, 102, ...
```

So lexicographical order begins:

```text
1
10
100
101
...
11
12
...
2
20
...
```

We do not need to build this tree.

We only need to count how many valid numbers are under a prefix.

For example, with:

```python
n = 13
```

the prefix `1` contains:

```text
1, 10, 11, 12, 13
```

So the subtree rooted at prefix `1` has size `5`.

If `k` is larger than this size, we can skip the entire prefix `1` subtree and move to prefix `2`.

If `k` lies inside this subtree, we go deeper from `1` to `10`.

## Counting Numbers Under a Prefix

To count how many numbers from `1` to `n` start with prefix `prefix`, compare ranges level by level.

For prefix `1`, the covered ranges are:

```text
[1, 2)
[10, 20)
[100, 200)
[1000, 2000)
...
```

Each range means numbers that start with that prefix at a certain digit length.

For a bound `n`, the count added at each level is:

```python
min(n + 1, next_prefix) - prefix
```

when this value is positive.

For example, `n = 13`, prefix `1`.

First level:

```text
[1, 2) gives 1
```

Second level:

```text
[10, 20) clipped by n + 1 = 14 gives [10, 14), count 4
```

Total:

```text
1 + 4 = 5
```

So there are 5 numbers starting with `1`.

## Algorithm

Start at:

```python
curr = 1
```

This is the first number in lexicographical order.

Since we are already standing on the first number, reduce `k` by one:

```python
k -= 1
```

While `k > 0`:

1. Count how many numbers are under prefix `curr`.
2. If that count is less than or equal to `k`, the answer is not inside this prefix subtree.
   - Skip the whole subtree.
   - Move to the next sibling: `curr += 1`.
   - Subtract the skipped count from `k`.
3. Otherwise, the answer is inside this prefix subtree.
   - Move to the first child: `curr *= 10`.
   - Subtract `1` from `k` because we visit that child prefix itself.

When `k == 0`, `curr` is the answer.

## Correctness

Lexicographical order over integers from `1` to `n` is equivalent to preorder traversal of the conceptual prefix tree.

At every step, `curr` represents the current prefix position in that traversal.

The helper count tells exactly how many valid numbers appear in the subtree rooted at `curr`.

If this subtree size is less than or equal to `k`, then the desired number occurs after every number in this subtree. Skipping the whole subtree and moving to `curr + 1` preserves the target position after subtracting the skipped size.

If this subtree size is greater than `k`, then the desired number lies inside the current subtree. In preorder traversal, after visiting `curr`, the next position inside the subtree is its first child `curr * 10`. Moving there and subtracting one correctly accounts for visiting that child prefix.

Each loop step either skips a complete subtree or moves one level deeper inside the subtree that contains the answer. These operations exactly follow preorder lexicographical order without enumerating every node.

When `k` becomes zero, the current number is exactly the target position, so returning `curr` is correct.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n * log n)` | Each move calls a prefix-count loop over digit levels |
| Space | `O(1)` | Only integer variables are used |

In practice this is very small because `n <= 10^9`, so there are at most 10 digit levels.

## Implementation

```python
class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count_prefix(prefix: int) -> int:
            count = 0
            first = prefix
            next_prefix = prefix + 1

            while first <= n:
                count += min(n + 1, next_prefix) - first

                first *= 10
                next_prefix *= 10

            return count

        curr = 1
        k -= 1

        while k > 0:
            steps = count_prefix(curr)

            if steps <= k:
                curr += 1
                k -= steps
            else:
                curr *= 10
                k -= 1

        return curr
```

## Code Explanation

The helper function counts how many valid numbers begin with a prefix:

```python
def count_prefix(prefix: int) -> int:
```

We use two boundaries:

```python
first = prefix
next_prefix = prefix + 1
```

For prefix `1`, these start as:

```text
first = 1
next_prefix = 2
```

The range `[first, next_prefix)` contains numbers starting with this prefix at the current digit level.

At each level, we clip the range by `n + 1`:

```python
count += min(n + 1, next_prefix) - first
```

Then we move one digit deeper:

```python
first *= 10
next_prefix *= 10
```

The main function starts at `1`:

```python
curr = 1
k -= 1
```

We subtract one because `1` is already the first number.

For each prefix, we count its subtree:

```python
steps = count_prefix(curr)
```

If the target is outside this subtree:

```python
if steps <= k:
    curr += 1
    k -= steps
```

we skip it.

Otherwise, the target is inside the subtree:

```python
else:
    curr *= 10
    k -= 1
```

We go deeper to the first child.

Finally, `curr` is the answer.

## Testing

```python
def brute(n, k):
    nums = list(range(1, n + 1))
    nums.sort(key=str)
    return nums[k - 1]

def run_tests():
    s = Solution()

    assert s.findKthNumber(13, 2) == 10

    assert s.findKthNumber(1, 1) == 1

    assert s.findKthNumber(100, 10) == 17

    assert s.findKthNumber(10, 3) == 2

    assert s.findKthNumber(99, 90) == brute(99, 90)

    assert s.findKthNumber(1000, 500) == brute(1000, 500)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 13, k = 2` | Checks official example |
| `n = 1, k = 1` | Checks smallest input |
| `n = 100, k = 10` | Checks deeper prefix `100` |
| `n = 10, k = 3` | Checks transition from `10` to `2` |
| Brute comparison | Validates against sorting for small inputs |
| Larger brute comparison | Checks many prefix skips |