K-th Smallest in Lexicographical Order

Intuition

• We consider a small example n = 20 to find patterns.
[1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30]
• 11 takes precedence over 2 and 20 takes precedence over 3.
• Generalizing, it appears we multiply by 10 greedily and attempt to fill in the "lowest level" before backtracking.
• This notion of backtracking clues us into using DFS.
• A TLE solution emerges here with DFS while decrementing k until we hit the correct value.
• In our depiction, we notice each level follows sequentially from the following. For the 10s, 1 handles 10 through 19, 2 handles 20 through 29, etc.
• The stopping point is dictated by the node in the following call's leftmost node .
• Instead of having to iterate through all the nodes we can find the difference between these values.

Flow

Small example → tle dfs → optimized dfs by jumping over calls.

Code

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        curr, k = 1, k - 1  # note k - 1
        
        def countSteps(n, prefix1, prefix2):
            steps = 0
            while prefix1 <= n:
                # get steps at this level
                # n + 1 for inclusivity
                steps += min(n + 1, prefix2) - prefix1  
                # move to next level of the tree
                prefix1 *= 10
                prefix2 *= 10
            return steps
        
        while k > 0:
            steps = countSteps(n, curr, curr + 1)
            # steps between current and following
            if steps <= k:
                curr += 1
                k -= steps
            else:
                curr *= 10
                k -= 1
        
        return curr

Editorial code above.