K-th Smallest in Lexicographical Order

Brute Force Solution

A naive approach would involve generating all numbers from 1 to n, sorting them lexicographically (as strings), and then returning the kth element. This is highly inefficient, especially for large values of n.

Code (Python)

def findKthNumber_brute_force(n: int, k: int) -> int:
    nums = list(map(str, range(1, n + 1)))
    nums.sort()
    return int(nums[k - 1])

• Time Complexity: O(n log n) due to sorting.
• Space Complexity: O(n) to store the numbers as strings.

This approach fails for larger values of n, as we will get a timeout.

Optimal Solution

A more efficient approach involves traversing the lexicographical tree. We start from 1 and explore its children (10, 11, 12,...), and so on, until we find the kth number.

We can use a function to calculate the number of nodes between two numbers in the lexicographical tree.

Algorithm:

1. Initialize curr = 1 (the starting number) and k = k - 1 (since we start from the first number).
2. Iterate until k becomes 0.
   • Calculate the number of steps from curr to curr + 1 using a helper function steps(n, curr, curr + 1).
   • If k >= steps, it means the kth number is not in the subtree rooted at curr. So, decrement k by steps and move to the next sibling (curr++).
   • Otherwise, the kth number is in the subtree rooted at curr. So, decrement k by 1 (move to the first child) and move to the first child (curr *= 10).
3. Return curr.

Helper Function steps(n, n1, n2):

This function calculates how many numbers are between n1 and n2 in the lexicographical order, without exceeding n.

• Initialize steps = 0.
• Iterate while n1 <= n:
  • Add min(n + 1, n2) - n1 to steps.
  • Multiply n1 and n2 by 10 to go to the next level in the lexicographical tree.
• Return steps.

Code (Python)

def findKthNumber(n: int, k: int) -> int:
    def steps(n: int, n1: int, n2: int) -> int:
        steps = 0
        while n1 <= n:
            steps += min(n + 1, n2) - n1
            n1 *= 10
            n2 *= 10
        return steps

    curr = 1
    k -= 1
    while k > 0:
        step = steps(n, curr, curr + 1)
        if step <= k:
            curr += 1
            k -= step
        else:
            curr *= 10
            k -= 1

    return curr

• Time Complexity: O(log n), because in each step, we are either moving to a sibling or a child, and the maximum depth of the lexicographical tree is log base 10 of n.
• Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases

• n = 1, k = 1: Returns 1.
• n = 13, k = 2: Returns 10.