⚡Flashcard Drill➔
NeetCode #941LC-440HardMath & Geometry
← Back to All Problems

#941 · #440 · K-th Smallest in Lexicographical Order(字典序的第 K 小数字)

📌 Problem Statement & Constraints

Given integers n and k, return the k-th number in the lexicographical ordering of the integers 1..n. Constraints: 1 <= k <= n <= 10^9.

💡 Core Algorithmic Approaches

  1. Model 1..n as a 10-ary tree (roots 1..9, children of x are 10x..10x+9); lexicographical order is pre-order traversal.
  2. Define count(prefix): how many nodes in the subtree rooted at prefix have value at most n.
  3. Walk from cur = 1 with k -= 1 (the current node counts as one). If count(cur) <= k, the target is outside this subtree: subtract the whole subtree and move right with cur += 1.
  4. Otherwise descend with cur *= 10 and k -= 1. count is computed level by level by intersecting [first, last] with n.

💻 Benchmark Python3 Implementation

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count(prefix: int) -> int:
            # number of nodes <= n in the subtree rooted at prefix
            total = 0
            first, last = prefix, prefix
            while first <= n:
                total += min(last, n) - first + 1
                first *= 10
                last = last * 10 + 9
            return total

        cur = 1
        k -= 1
        while k > 0:
            cnt = count(cur)
            if cnt <= k:
                k -= cnt
                cur += 1              # skip this subtree, move to the sibling
            else:
                cur *= 10             # descend into the subtree
                k -= 1
        return cur

⚡ Complexity Deep Dive

⏱️ Time Complexity
O((log n)^2): O(log n) levels, each calling a count that is O(log n).
💾 Space Complexity
O(1): constant state.

⚠️ Interview Pitfalls & Follow-ups

  • Generating 1..n and sorting: n can be 10^9, so this is impossible.
  • Forgetting last = last * 10 + 9 in count: the level interval is not updated and the count is wrong.
  • Getting the k -= 1 placement wrong: descending into a child consumes the current node, so k must decrease by 1.
  • Starting cur at 0: 0 is not part of the range.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems