Start by exploring numbers from 1 to 9 recursively, appending digits in a depth-first manner to maintain lexicographical order. Use a trie-like approach to simulate prefix expansions without extra space. This guarantees O(n) time traversal while generating the exact sequence needed for this problem, avoiding sorting after generation.
Problem Statement
Given an integer n, return all integers in the range [1, n] sorted in lexicographical order. Your solution must efficiently generate the sequence without using built-in sorting methods.
Design an algorithm that uses depth-first search to traverse numbers as if building a trie of digits. The algorithm should achieve O(n) time complexity with O(1) extra space, outputting the full lexicographical list.
Examples
Example 1
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example details omitted.
Example 2
Input: n = 2
Output: [1,2]
Example details omitted.
Constraints
- 1 <= n <= 5 * 104
Solution Approach
Recursive Depth-First Search with Prefix Expansion
Begin with numbers 1 through 9 and recursively append digits 0 through 9 to each prefix. Stop recursion when the generated number exceeds n. This DFS traversal mimics a trie structure where each node represents a digit prefix.
Iterative Simulation of Trie Traversal
Instead of using recursion stack, maintain a current number and repeatedly multiply by 10 to explore deeper prefixes. When reaching a number larger than n, increment and trim trailing zeros to move to the next lexicographical number.
Avoid Extra Space Beyond Output List
Do not construct a full tree or additional arrays. Only track the current number during traversal. This approach ensures O(1) extra space while the output list naturally accumulates numbers in lexicographical order.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Time complexity is O(n) because each number from 1 to n is visited exactly once during DFS traversal. Space complexity is O(1) beyond the output list since only a single integer is tracked during iteration or recursion, avoiding extra data structures.
What Interviewers Usually Probe
- Asks how to generate numbers without sorting the final list.
- Checks understanding of DFS traversal applied to number prefixes.
- Tests ability to optimize space usage for large n values.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to stop recursion when the number exceeds n.
- Using built-in sort instead of generating numbers lexicographically.
- Exceeding space limits by storing unnecessary intermediate data structures.
Follow-up variants
- Generate numbers in reverse lexicographical order using the same DFS-trie pattern.
- Limit the output to numbers containing a specific digit while maintaining lexicographical order.
- Adapt the approach for a range [m, n] instead of starting from 1, adjusting prefix exploration accordingly.
How GhostInterview Helps
- GhostInterview walks through DFS and trie prefix expansion step by step, ensuring correct lexicographical output.
- It identifies off-by-one or overflow errors during prefix recursion to prevent invalid numbers.
- Provides iterative simulation techniques to maintain O(1) space and optimize large n cases efficiently.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the key pattern for solving Lexicographical Numbers?
The problem uses a depth-first search pattern combined with trie-like prefix expansion to generate numbers lexicographically.
Can this be solved without recursion?
Yes, iterative traversal multiplying by 10 and adjusting numbers simulates the DFS-trie pattern without recursion, preserving O(1) space.
Why can't we just sort numbers from 1 to n?
Sorting adds O(n log n) time and extra space, whereas DFS-trie traversal achieves O(n) time and minimal space.
What are common mistakes in this problem?
Exceeding n during recursion, forgetting to handle trailing zeros, or using extra arrays for prefixes are typical pitfalls.
Does this pattern work for very large n, like 50000?
Yes, following the DFS-trie approach carefully ensures O(n) traversal with O(1) extra space, suitable even for the upper constraint.
Need direct help with Lexicographical Numbers instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Lexicographical Numbers from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find concatenated words by using dynamic programming and depth-first search to identify valid words made of other words in the list.
Open problem page#211 Design Add and Search Words Data StructureBuild a WordDictionary supporting dynamic word addition and search with wildcard matching efficiently using Trie and DFS.
Open problem page#676 Implement Magic DictionaryDesign a Magic Dictionary to allow searching with one-character modifications, using Hash Table and String techniques.
Open problem page