Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Lexicographical order is a preorder traversal of decimal prefixes. Every number beginning with a prefix forms one contiguous block. If we can count that block without listing it, we can skip it entirely when the desired rank lies beyond it.

Approach

Start at prefix one and decrease k by one so it counts the remaining traversal steps.
Count numbers under the current prefix using half-open intervals [prefix, prefix + 1), then intervals with both boundaries multiplied by ten. Clip each interval's upper boundary at n + 1.
If the block's size is at most the remaining k, subtract its size and advance to the next sibling prefix.
Otherwise the answer lies inside the block. Descend to its first child by multiplying the prefix by ten and subtract one for passing the prefix itself.
When no steps remain, return the current number. Equality in the skip condition correctly places the answer at the next prefix.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        curr = 1
        k -= 1

        def get_steps(b1, b2):
            count = 0

            while b1 <= n:
                if b2 <= n + 1:
                    count += min(n + 1, b2) - b1
                else:
                    count += n + 1 - b1
                b1 *= 10
                b2 *= 10

            return count

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

        return curr

Complexity analysis

Let d be the number of decimal digits in n. Prefix counting costs O(d) per tree move, and only O(d) sibling/child moves are needed, for O(d²) = O((log n)²) time and O(1) auxiliary space.