Naive Solution

A naive approach would involve generating all integers from 1 to n, sorting them lexicographically, and then returning the kth element. However, this approach is inefficient, especially for large values of n, as it requires storing all numbers in memory and sorting them.

Code (Python)

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

Time Complexity

O(n log n), due to sorting n elements.

Space Complexity

O(n), to store the numbers in a list.

Optimal Solution

A more efficient approach is to use a depth-first search (DFS) strategy to traverse the lexicographical tree. We can determine how many numbers start with a given prefix. Based on this count, we can decide whether to move to the next prefix or to go deeper into the current prefix.

Algorithm

1. Initialize curr to 1 (the starting number).
2. Iterate k times:
   • Calculate the number of steps (how many numbers) are between curr and curr + 1 in the lexicographical order. We can name the number of steps as steps.
   • If steps <= k: It means the kth number is not in the subtree of curr, so we decrement k by steps and increment curr by 1 (move to the next sibling).
   • Else: It means the kth number is in the subtree of curr, so we decrement k by 1 (move to the next child) and multiply curr by 10.
3. Return curr.

Helper Function: calSteps

This function calculates the number of integers between two numbers (inclusive) in lexicographical order. In other words, given n and two numbers, n1 and n2, how many numbers are between n1 and n2 which are less or equal to n.

Code (Python)

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

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

Example

Let's trace the optimal solution with n = 13 and k = 2.

1. curr = 1, k = 1.
2. steps = calSteps(13, 1, 2) = 11 (1, 10, 11, 12, 13).
3. Since steps > k, curr = 10, k = 0.
4. The loop terminates.
5. Return curr = 10.

Time Complexity

O(log n), where n is the given integer. The calSteps function takes O(1) since the number of steps is at most O(log n). The outer loop iterates until k = 0, and in the worst case, it would take O(log n) iterations to find the k-th lexicographical number.

Space Complexity

O(1), as we use only a constant amount of extra space.

Edge Cases

• n = 1, k = 1: The function should return 1.
• n is very large (e.g., 10⁹): The algorithm should still work efficiently without causing overflow.
• k = 1: The function should return 1.