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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K-th Smallest in Lexicographical Order

Difficulty: Hard

Problem Description

Given two integers n and k, return the k-th lexicographically smallest integer in the range [1, n].

Key Insights

  • Lexicographical order is similar to alphabetical order but applied to numbers.
  • The k-th number can be found without generating all numbers in the range.
  • A Trie-like traversal can be used to navigate through the potential numbers in lexicographical order efficiently.

Space and Time Complexity

Time Complexity: O(log n) - Each step in the traversal reduces the search space significantly. Space Complexity: O(1) - Only a few variables are used to keep track of the current state.

Solution

To solve this problem, we can utilize a depth-first search (DFS) approach to explore the lexicographical order of numbers. Starting from the smallest number, we can count how many numbers can be formed with the current prefix. If the count is less than k, we move to the next prefix. If the count is greater than or equal to k, we dive deeper into the current prefix. This allows us to find the k-th smallest number efficiently without creating a complete list of numbers.

Code Solutions

def findKthNumber(n: int, k: int) -> int:
    current = 1
    k -= 1  # We start from the first number which is 1
    while k > 0:
        count = 0
        first = current
        last = current + 1
        while first <= n:
            count += min(n + 1, last) - first  # Count numbers in the range [first, last)
            first *= 10  # Move to the next level
            last *= 10  # Move to the next level
        if count <= k:
            current += 1  # Move to the next prefix
            k -= count
        else:
            current *= 10  # Go deeper into the current prefix
    return current
← Back to All Questions