Problem statement

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/

Solution

Logical extension of Problem 0386. Lexicographical Numbers.

Let findStart(n, start)} be a function which evaluates number of numbers <= n, which starts from start. We can evaluate this function in O(s), where s` is length of number.

Now, we can evaluate how many numbers starts with 1, with 2, and so on, with 9, and we can understand which is the first digit, for example 3, then we find how many numbers starts with 30, 31 and so on 39, find the second digit and so on.

Complexity

Overall time complexity of algorithm is O(9s^2) = O(9 * log^2n), space complexity is O(s).

Code

class Solution:
    def findKthNumber(self, n, k):
        def findStart(n, start):  #n, start: strings
            if n == start: return 1
            a, b = len(n), len(start)
            ans = (10**(a - b) - 1)//9
            if n.startswith(start):
                ans += int(n[b:]) + 1
            elif n[:b] > start:
                ans += 10**(a - b)
            return ans
        
        found = ""
        while k != 0:
            start = 1 if len(found) == 0 else 0
            k -= 1    #for number found itself
            for i in range(start, 10):   #check cases found + "0", ..., found + "9"
                att = findStart(str(n), str(found) + str(i))
                if att <= k:
                    k -= att
                else:
                    found += str(i)
                    break

        return int(found)

Remark

We can visualize our numbers as trie, where we need to find k- th element in in-order traversal.