We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-th Smallest in Lexicographical Order

Number: 440

Difficulty: Hard

Paid? No

Companies: TikTok, Google, DE Shaw, Meta, Hulu

Problem Description

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n]. For instance, when n = 13 and k = 2, the lexicographical order of numbers is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the answer is 10.

Key Insights

  • Visualize the set [1, n] as being organized in a trie-like structure rooted by their prefixes.
  • Instead of sorting or enumerating all numbers, count how many nodes (numbers) exist under a given prefix.
  • Use counting to decide if the kth number lies within the current prefix subtree or if we need to skip to the next sibling.
  • A helper method computes the number of nodes within a prefix interval while respecting the upper bound n.

Space and Time Complexity

Time Complexity: Approximately O(log(n) * log(n)). At each step, the counting process runs in O(log(n)) and there are roughly O(log(n)) steps. Space Complexity: O(1) extra space.

Solution

We traverse the lexicographical tree without constructing its full structure. Start with the first number, 1, then repeatedly count the number of numbers (steps) under the current prefix. If the number of steps under the prefix is less than or equal to k, it means the kth number is not in this subtree, so we skip it by moving to the next prefix. Otherwise, we dive into the subtree by appending a digit (multiplying the prefix by 10) and decrement k accordingly. This approach efficiently finds the kth lexicographical number.

Code Solutions

def findKthNumber(n: int, k: int) -> int:
    # Start at the root of the lexicographical tree.
    current = 1
    k -= 1  # We've accounted for the first number (1).
    
    # Helper function to count nodes under the given prefix.
    def count_steps(n: int, prefix: int) -> int:
        steps = 0
        first = prefix
        last = prefix
        while first <= n:
            steps += min(n, last) - first + 1
            first *= 10
            last = last * 10 + 9
        return steps
    
    # Traverse the lexicographical tree.
    while k > 0:
        steps = count_steps(n, current)
        # If k is larger than the steps in the current subtree, skip it.
        if k >= steps:
            k -= steps
            current += 1
        else:
            # Otherwise, move down one level.
            current *= 10
            k -= 1  # Count the move as one step.
    return current

# Example usage:
print(findKthNumber(13, 2))  # Output: 10
← Back to All Questions