440. K-th Smallest in Lexicographical Order

Time: O(log² n)

Space: O(1)

Intuition

Numbers 1..n in lexicographic order form a 10-ary prefix trie. Count how many numbers fall under a given prefix to decide whether to go deeper or to the next sibling.

Algorithm

1Start at curr=1, steps taken=1.
2While steps < k: count numbers in the subtree rooted at curr (capped at n); if count ≤ k-steps, skip the whole subtree (curr++, steps+=count); else go deeper (curr*=10, steps++).
3Return curr.

Common Pitfalls

•Count uses long arithmetic to avoid overflow when computing prefix boundaries.

440.cs

// Approach: Trie navigation — count how many numbers fall under the current
// prefix; jump to the next prefix or descend one level based on k remaining.
// Time: O(log² n) Space: O(1)

public class Solution
{
    public int FindKthNumber(int n, int k)
    {
        k--;
        long curr = 1;
        while (k > 0)
        {
            long count = CountNodes(curr, n);
            if (k >= count)
            {
                curr++;
                k -= (int)count;
            }
            else
            {
                curr *= 10;
                k--;
            }
        }

        return (int)curr;
    }

    private long CountNodes(long curr, int n)
    {
        long next = curr + 1;
        long result = 0;
        while (curr <= n)
        {
            result += Math.Min(n - curr + 1, next - curr);
            curr *= 10;
            next *= 10;
        }

        return result;
    }
}

Was this solution helpful?