K-th Smallest in Lexicographical Order

Given two integers n and k, return the k<sup>th</sup> lexicographically smallest integer in the range [1, n]. Consider these examples:

Example 1: 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: n = 1, k = 1 Output: 1

Constraints: 1 <= k <= n <= 10⁹

def findKthNumber(n: int, k: int) -> int:
    """Finds the kth lexicographically smallest integer in the range [1, n].

    Args:
        n: The upper bound of the range.
        k: The desired rank (1-indexed).

    Returns:
        The kth lexicographically smallest integer.
    """

    def get_count(prefix: int, n: int) -> int:
        """Calculates how many numbers are under the prefix.

        Args:
            prefix: The current prefix.
            n: The upper bound.

        Returns:
            The count of numbers under the prefix.
        """
        count = 0
        curr = prefix
        next_num = prefix + 1

        while curr <= n:
            count += min(n + 1, next_num) - curr
            curr *= 10
            next_num *= 10

        return count

    curr = 1
    k -= 1  # Adjust k to be 0-indexed

    while k > 0:
        count = get_count(curr, n)

        if k >= count:
            curr += 1
            k -= count
        else:
            curr *= 10
            k -= 1

    return curr


# Example usage:
n = 13
k = 2
result = findKthNumber(n, k)
print(f"The {k + 1}th lexicographically smallest number in [1, {n}] is: {result}")  # Output: 10

n = 1
k = 1
result = findKthNumber(n, k)
print(f"The {k + 1}th lexicographically smallest number in [1, {n}] is: {result}")  # Output: 1

Brute-Force Solution (Not Efficient for Large n)

A naive approach would involve generating all numbers from 1 to n, sorting them lexicographically (as strings), and then returning the k-th element. This is inefficient for larger values of n because sorting all numbers will take a lot of time and space.

def findKthNumber_brute_force(n: int, k: int) -> int:
    """Brute-force solution to find the kth lexicographically smallest integer.
    Inefficient for large n.
    """
    numbers = list(range(1, n + 1))
    numbers.sort(key=str)
    return numbers[k - 1]

Optimal Solution: Lexicographical Tree Traversal

The optimal solution treats the problem as traversing a 10-ary tree where each node's children are its multiples by 10 plus digits from 0 to 9. The algorithm efficiently determines which branch to follow to reach the k-th smallest number without generating all numbers.

1. get_count(prefix, n) function: This function calculates how many numbers exist in the range [1, n] that have prefix as their prefix. It helps to determine how many numbers lie under a given node in the 10-ary tree.
2. Main Algorithm:
   • Start with curr = 1 (the root of the tree) and adjust k to be 0-indexed.
   • Iteratively, calculate the number of nodes under the current prefix using get_count().
   • If k is greater than the count, it means the k-th number is not under the current prefix, so we move to the next prefix (curr += 1) and reduce k by count.
   • Otherwise, the k-th number is under the current prefix, so we move one level deeper into the tree (curr *= 10) and decrement k by 1.
   • Repeat until k becomes 0. At that point, curr will be the k-th lexicographically smallest number.

Big(O) Runtime Analysis

The time complexity is O(log n * log n). The outer while loop runs until k becomes 0. In the worst case, k can be close to n. The get_count function has a while loop that iterates at most log10(n) times. The outer loop also iterates a maximum of n times, so the complexity is closer to O(log n * log n) because the get_count is O(log n) and dominates the inner loop's operations.

Big(O) Space Usage Analysis

The space complexity is O(1) because the algorithm uses a constant amount of extra space, regardless of the input size n and k. It only uses a few integer variables (curr, k, count, prefix, next_num) to keep track of the current number, the remaining rank, and counts during the traversal.

Edge Cases

1. n = 1, k = 1: The algorithm correctly returns 1.
2. n is a small number and k is close to n: The algorithm efficiently finds the k-th number without generating all numbers.
3. k = 1: The algorithm should quickly return 1 since 1 is always the smallest lexicographical number.
4. k = n: The algorithm should traverse to the last number, which might require several iterations but will still be within the logarithmic time complexity.