440. K-th Smallest in Lexicographical Order

Description

Given two integers n and k, return the k^th 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 <= 10⁹

Solutions

Solution 1: Trie-Based Counting + Greedy Construction

Thinking

$n$ can be $10^9$, so we cannot list and sort. Lexicographic order is a $10$-ary trie: the children of $x$ are $10x,\ldots,10x+9$ that stay $\le n$.

Count the subtree of a prefix $curr$ by intersecting $[curr,curr+1)$ with $[1,n]$ at each extra digit. If that count is $\le k$, skip the whole tree and increment $curr$; otherwise step into $curr\times 10$ and spend one for the prefix itself.

Decrement $k$ once at the start because we already stand on $1$. Layered counting never enumerates every integer in the subtree.

The problem asks for the $k$-th smallest number in the range $[1, n]$ when all numbers are sorted in lexicographical order. Since $n$ can be as large as $10^9$, we cannot afford to generate and sort all the numbers explicitly. Instead, we adopt a strategy based on greedy traversal over a conceptual Trie.

We treat the range $[1, n]$ as a 10-ary prefix tree (Trie):

Each node represents a numeric prefix, starting from an empty root;
Each node has 10 children, corresponding to appending digits $0 \sim 9$;
For example, prefix $1$ has children $10, 11, \ldots, 19$, and node $10$ has children $100, 101, \ldots, 109$;
This tree naturally reflects lexicographical order traversal.

root
├── 1
│   ├── 10
│   ├── 11
│   ├── ...
├── 2
├── ...

We use a variable $\textit{curr}$ to denote the current prefix, initialized as $1$. At each step, we try to expand or skip prefixes until we find the $k$-th smallest number.

At each step, we calculate how many valid numbers (i.e., numbers $\le n$ with prefix $\textit{curr}$) exist under this prefix subtree. Let this count be $\textit{count}(\text{curr})$:

If $k \ge \text{count}(\text{curr})$: the target number is not in this subtree. We skip the entire subtree by moving to the next sibling:

\[ \textit{curr} \leftarrow \textit{curr} + 1,\quad k \leftarrow k - \text{count}(\text{curr}) \]
Otherwise: the target is within this subtree. We go one level deeper:

\[ \textit{curr} \leftarrow \textit{curr} \times 10,\quad k \leftarrow k - 1 \]

At each level, we enlarge the current range by multiplying by 10 and continue descending until we exceed $n$.

The time complexity is $O(\log^2 n)$, as we perform logarithmic operations for counting and traversing the Trie structure. The space complexity is $O(1)$ since we only use a few variables to track the current prefix and count.

Python3JavaC++GoTypeScriptRust

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

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;
    }
}

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;
    }
};

func findKthNumber(n int, k int) int {
    count := func(curr int) int {
        next := curr + 1
        cnt := 0
        for curr <= n {
            cnt += min(n-curr+1, next-curr)
            next *= 10
            curr *= 10
        }
        return cnt
    }
    curr := 1
    k--
    for k > 0 {
        cnt := count(curr)
        if k >= cnt {
            k -= cnt
            curr++
        } else {
            k--
            curr *= 10
        }
    }
    return curr
}

function findKthNumber(n: number, k: number): number {
    function count(curr: number): number {
        let next = curr + 1;
        let cnt = 0;
        while (curr <= n) {
            cnt += Math.min(n - curr + 1, next - curr);
            curr *= 10;
            next *= 10;
        }
        return cnt;
    }

    let curr = 1;
    k--;

    while (k > 0) {
        const cnt = count(curr);
        if (k >= cnt) {
            k -= cnt;
            curr += 1;
        } else {
            k -= 1;
            curr *= 10;
        }
    }

    return curr;
}

impl Solution {
    pub fn find_kth_number(n: i32, k: i32) -> i32 {
        fn count(mut curr: i64, n: i32) -> i32 {
            let mut next = curr + 1;
            let mut total = 0;
            let n = n as i64;
            while curr <= n {
                total += std::cmp::min(n - curr + 1, next - curr);
                curr *= 10;
                next *= 10;
            }
            total as i32
        }

        let mut curr = 1;
        let mut k = k - 1;

        while k > 0 {
            let cnt = count(curr as i64, n);
            if k >= cnt {
                k -= cnt;
                curr += 1;
            } else {
                k -= 1;
                curr *= 10;
            }
        }

        curr
    }
}

440. K-th Smallest in Lexicographical Order

Description

Solutions

Solution 1: Trie-Based Counting + Greedy Construction

Comments