NeetCode #931LC-386MediumMath & Geometry
← Back to All Problems#931 · #386 · Lexicographical Numbers(字典序排数)
📌 Problem Statement & Constraints
Given an integer
n, return all integers from 1 to n sorted in lexicographical order. The solution should run in O(n) time and use O(1) extra space excluding the output. Constraints: 1 <= n <= 5 * 10^4.💡 Core Algorithmic Approaches
- View
1..nas a 10-ary tree: the roots are1..9and nodekhas children10k, 10k+1, ..., 10k+9. - Lexicographical order is exactly the pre-order traversal of this tree.
- Simulate the traversal with a single integer
cur: descend withcur *= 10whilecur * 10 <= n, otherwise step right withcur += 1. - When
curends in 9 orcur + 1 > n, backtrack withcur //= 10until a right step is legal again.
💻 Benchmark Python3 Implementation
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = []
cur = 1
for _ in range(n):
res.append(cur)
if cur * 10 <= n:
cur *= 10 # descend into children
else:
while cur % 10 == 9 or cur + 1 > n:
cur //= 10 # backtrack to a node that can move right
cur += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each integer is visited once.
💾 Space Complexity
O(1) excluding the output.
⚠️ Interview Pitfalls & Follow-ups
- Sorting
range(1, n + 1)by string: O(n log n) time and O(n) string storage, violating the stated bounds. - Checking only
cur % 10 == 9when backtracking: the boundcur + 1 > nalso forces a backtrack. - Backtracking only one level: the
whileis required because several levels may need to unwind. - Starting
curat 0: 0 is not part of the output; start at 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.