[Leetcode] 440. K-th Smallest in Lexicographical Order (HARD)

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/?envType=daily-question&envId=2025-06-09

initial

So there is dfs way to calculate nth number of lexicographical ascending order

this dfs way is like traversing a tree of preorder traversal root->left->right

        (root)
       / | \ ...
      1  2  3
     / \
    10 11
   / \
  100 101

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        count=0
        ans=0
        # 1 10 100 101 102 103 11 110 111 112 113
        def dfs(num):
            nonlocal count,ans
            count+=1
            if count==k:
                ans=num
                return
            for i in range(10):
                nextNum= num*10+i
                if nextNum<=n:
                    dfs(nextNum)

        for i in range(1,10):
            if n>=i:
                dfs(i)
        return ans

or the iterative way but still tle

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        count=0
        curNum=1
        # 1 10 100 101 102 103 11 110 111 112 113
        for _ in range(n):
            count+=1
            if count==k:
                break

            if curNum*10<=n:
                curNum*=10
            else:
                if curNum>=n:
                    curNum = curNum//10
                curNum+=1
                while curNum%10==0:
                    curNum = curNum//10
            
        return curNum

sol

so logic is quite hard. even harder than iterative. But it is still using the same logic of counting all valid numbers within the subtree using preorder traversal. Using [curNum, curNum+1] intervals, we can rapidly calculate how many numbers can be prefixed with curNum with this

count+= min(n+1, interval[1])-interval[0]

For curNum = 1, it sums up numbers like 1, then 10-19, then 100-199, and so on, stopping at n. The count for curNum=1 (with n=13) is 5 (1, 10, 11, 12, 13).

Then, even if count is not enough like it is less than k, we need to increment curNum by 1 to search for the next subtree. This is cuz currrent subtree does not produce enough numbers that can be prefixed with current number.

Else, there is indeed a value in the current subtree. So we multiply curNum by 10 and search deeper into the subtree. But i dont get why we k-=1 and not k minus the current level of the subtree like if it is 10 and there is 10,11,12 we should minus 3?

Correction: oh it is just k-=1 cuz for example if we are going from 1 to 10, we are saying we choose 1 as part of the path. We dont do k-=3 even when curNum=10 cuz we are not skipping 10,11,12.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        k-=1
        curNum=1
        # 1 10 100 101 102 103 11 110 111 112 113
        while k:
            count=0
            interval=[curNum,curNum+1]
            while interval[0]<=n:
                count+= min(n+1, interval[1])-interval[0]
                interval = [10*interval[0],10*interval[1]]
            if k>=count:
                curNum+=1
                k-=count
            else:
                curNum*=10
                k-=1
        return curNum

complexity

It's quite common to find logarithmic time complexities tricky, especially when they are nested! Let's break down why the time complexity of this algorithm is $O((\log N)^2)$.

Revisit the "Denary Tree" of Numbers

Imagine the numbers from 1 to N organized in a tree structure:

          (Root - conceptual)
          / | \ ... \
         1  2  3 ...  9
        /|\   /|\
       10 11 20 21
      /
     100
     ...

Lexicographical order is simply a pre-order traversal of this tree (visit root, then its children from left to right).

The Two Main Loops

Your code has two nested while loops that determine the time complexity:

1. Outer while k > 0 loop: This loop makes "major decisions" about our path in the tree.
2. Inner while interval[0] <= n loop: This loop calculates the count (the number of nodes in a branch/subtree).

Let's analyze each one:

---

1. The Outer Loop (while k > 0)

• What it does: In each iteration, result either:

  • Gets multiplied by 10 (result *= 10): This means we are going one level deeper into the tree (e.g., from 1 to 10, or 12 to 120).
  • Gets incremented by 1 (result += 1): This means we are moving sideways to the next sibling node at the current level (e.g., from 1 to 2, or 10 to 11, or 19 (backtracking) to 2).

• How many iterations?

  • Depth (Multiplying by 10): The maximum depth of this tree is determined by the number of digits in N. If N = 10^9, it has 10 digits. To go from 1 to 1,000,000,000 (which is $10^9$), you multiply by 10 nine times. This is $O(\log_{10} N)$ steps.
  • Width (Incrementing by 1): At each depth level, result might need to increment multiple times (e.g., 1 -> 2 -> ... -> 9). In the worst case, result might need to jump from 1... to 9.... However, k is simultaneously decreasing. Across all levels, the total number of times result increments by 1 is also bounded.
  • Overall: The result variable is either increasing its number of digits or increasing its value within the current number of digits. Both of these combined ensure that result grows towards N. The number of "major decisions" (iterations of the outer loop) is roughly proportional to the number of digits in N, multiplied by a small constant (for the 9 possible siblings at each level). So, the outer loop runs approximately $O(\log N)$ times.

---

2. The Inner Loop (while interval[0] <= n)

• What it does: This loop calculates the count of numbers in a particular branch. It starts with interval[0] (which is equal to result at the beginning of the inner loop) and repeatedly multiplies interval[0] by 10.
• How many iterations?
  • If result is 1, interval[0] will take values 1, 10, 100, 1000, ..., until it exceeds N.
  • The number of times you can multiply 1 by 10 before it exceeds N is precisely the number of digits in N (or more accurately, $O(\log_{10} N)$).
  • Therefore, the inner loop always runs approximately $O(\log N)$ times.

---

Combining Them: $O((\log N)^2)$

space is 1