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:

n = 13

the numbers in lexicographical order are:

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

So when:

k = 2

the answer is:

10

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

Input and Output

Example function shape:

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

Examples

Example 1:

n = 13
k = 2

Lexicographical order:

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

The second number is:

10

Example 2:

n = 1
k = 1

There is only one number:

[1]

Answer:

1

Example 3:

n = 100
k = 10

The beginning of lexicographical order is:

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

So the answer is:

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:

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:

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

Node 1 has children:

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

Node 10 has children:

100, 101, 102, ...

So lexicographical order begins:

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:

n = 13

the prefix 1 contains:

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:

[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:

min(n + 1, next_prefix) - prefix

when this value is positive.

For example, n = 13, prefix 1.

First level:

[1, 2) gives 1

Second level:

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

Total:

1 + 4 = 5

So there are 5 numbers starting with 1.

Algorithm

Start at:

curr = 1

This is the first number in lexicographical order.

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

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

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

Implementation

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:

def count_prefix(prefix: int) -> int:

We use two boundaries:

first = prefix
next_prefix = prefix + 1

For prefix 1, these start as:

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:

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

Then we move one digit deeper:

first *= 10
next_prefix *= 10

The main function starts at 1:

curr = 1
k -= 1

We subtract one because 1 is already the first number.

For each prefix, we count its subtree:

steps = count_prefix(curr)

If the target is outside this subtree:

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

we skip it.

Otherwise, the target is inside the subtree:

else:
    curr *= 10
    k -= 1

We go deeper to the first child.

Finally, curr is the answer.

Testing

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: