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
- Model
1..nas a 10-ary tree (roots1..9, children ofxare10x..10x+9); lexicographical order is pre-order traversal. - Define
count(prefix): how many nodes in the subtree rooted atprefixhave value at mostn. - Walk from
cur = 1withk -= 1(the current node counts as one). Ifcount(cur) <= k, the target is outside this subtree: subtract the whole subtree and move right withcur += 1. - Otherwise descend with
cur *= 10andk -= 1.countis computed level by level by intersecting[first, last]withn.
💻 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..nand sorting:ncan be10^9, so this is impossible. - Forgetting
last = last * 10 + 9incount: the level interval is not updated and the count is wrong. - Getting the
k -= 1placement wrong: descending into a child consumes the current node, sokmust decrease by 1. - Starting
curat 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.