⚡Flashcard Drill➔
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

  1. View 1..n as a 10-ary tree: the roots are 1..9 and node k has children 10k, 10k+1, ..., 10k+9.
  2. Lexicographical order is exactly the pre-order traversal of this tree.
  3. Simulate the traversal with a single integer cur: descend with cur *= 10 while cur * 10 <= n, otherwise step right with cur += 1.
  4. When cur ends in 9 or cur + 1 > n, backtrack with cur //= 10 until 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 == 9 when backtracking: the bound cur + 1 > n also forces a backtrack.
  • Backtracking only one level: the while is required because several levels may need to unwind.
  • Starting cur at 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems