386. Lexicographical Numbers - Detailed Explanation
Problem Statement
Given an integer n
, return all the numbers in the range [1, n]
sorted in lexicographical (dictionary) order. In lexicographical order, numbers are ordered as if they were strings (so "10" comes before "2" because '1' is alphabetically before '2').
Example 1:
Input: n = 13
Output: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: The numbers are ordered as strings in dictionary order. For example, "10" appears before "2" (because '1' comes before '2' lexicographically).
Example 2:
Input: n = 25
Output: [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 3, 4, 5, 6, 7, 8, 9]
This output sequence is the numbers 1 through 25 arranged as if sorting their decimal representations alphabetically.
Constraints:
1 <= n <= 5000
- The solution should be efficient (ideally O(n)) and should avoid naive string sorting for large n.
Hints to Solve the Problem
- Brute Force Approach: Convert all numbers to strings, sort them lexicographically, and then convert back to integers. (Simple but less efficient due to sorting overhead.)
- Optimized Approach: Generate numbers in lexicographical order directly without sorting. This can be done using a Depth-First Search (DFS) pattern or iterative technique to build the sequence.
Approach 1: Brute Force (Sort as Strings)
Explanation:
This straightforward approach generates all numbers from 1 to n and sorts them based on their string values (dictionary order):
- Create a list of numbers from 1 through n.
- Convert each number to a string and sort the list of strings lexicographically.
- Convert the sorted strings back to integers.
This leverages the built-in sorting but treats numbers as strings for ordering, achieving the lexicographical sequence.
Python Code:
Complexity Analysis:
- Time Complexity: ~O(N log N). Sorting N elements takes O(N log N) comparisons; comparing numbers as strings can add overhead proportional to their length (up to ~O(log₁₀ N) characters per number). For reasonable n (like 5000), this is fine, but it’s not linear time.
- Space Complexity: O(N) to store the list of numbers (and additional O(N) for their string representations during sort).
Java Code
Approach 2: Optimized DFS (Lexicographical Traversal)
Explanation:
This approach generates the lexicographical order directly using Depth-First Search (DFS) recursion (or an analogous iterative method):
-
Idea: Treat the sequence of numbers like a 10-ary tree (a prefix tree of decimal digits). Each number is a node, and appending any digit [0-9] to it leads to potential children. A DFS on this conceptual tree will naturally traverse numbers in lexicographical order.
-
Start from each number 1 through 9 as a "root" (because those are the first digits possible for positive integers).
-
For a current number
curr
, first appendcurr
to the result. Then try to generate its children by multiplyingcurr
by 10 and adding digits 0 through 9 (curr*10, curr*10+1, ..., curr*10+9
), as long as the result does not exceedn
. -
Recursively apply this process. This way, after outputting
1
, you recursively output10, 100, 1000, ...
then backtrack to11, 12, ...
and so on, achieving lexicographical order without explicit sorting. -
Termination: If the next number to explore is greater than
n
, stop exploring that branch (prune the recursion).
This DFS approach visits each number exactly once in the correct order, yielding an efficient generation in O(n) time.
Python Code:
Complexity Analysis:
-
Time Complexity: O(N). Each number from 1 to n is processed exactly once (added to the result and possibly used to generate descendants). The DFS traversal does a constant amount of work per number (aside from recursion overhead). This meets the requirement for an efficient solution.
-
Space Complexity: O(N). The output list holds all numbers 1 to n. The recursion stack depth can be at most the number of digits in n (e.g., for n=5000, at most 4 or 5 levels deep), which is negligible compared to N. Overall additional space is linear in N for the result list.
Java Implementation
Edge Cases
- n = 1 (Minimum Input): Should return
[1]
– trivial case with only one number. - n = 10 or 100 (Boundary of a power of 10): The sequence should handle transitions like
... , 9, 10, 11, ...
correctly. For example,n=10
should give[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]
. - Large n (e.g., n = 5000): The DFS approach should efficiently generate the list without timing out or using excessive memory. The result for n=5000 will start
[1, 10, 100, 1000, ...]
and so on, and it will include all numbers up to 5000.
Common Mistakes
- Using String Sorting Unnecessarily: While converting to strings and sorting works, it is not optimal for larger ranges. Forgetting that a direct generation method exists can lead to higher time complexity.
- Incorrect DFS Termination: Not stopping the DFS recursion when the number exceeds
n
. This can cause the algorithm to explore invalid numbers or even enter an infinite loop (for instance, continuing to multiply by 10 without a boundary check). Always ensure youreturn
orbreak
whencurr > n
ornext_num > n
. - Assuming Numerical Order: Remember that lexicographical order is different from numeric order. Simply listing 1 to n in increasing numeric order would be wrong for this problem (e.g., numeric order 1,2,3... vs lexicographic order 1,10,11...). It's important to treat numbers as strings for ordering or generate accordingly.
Related Problems for Practice
- Print Numbers from 1 to N: A simpler problem where you just output numbers 1 through N (can be solved via recursion or iteration; helps understand basic recursion which is extended in lexicographical order problem).
- Lexicographical Order Traversal: Traversal of tree or trie data structures in lexicographical order (similar concept of ordered DFS on prefixes, which is essentially what we do here with number prefixes).
- Iterative vs Recursive DFS: Understanding how to implement DFS both recursively and iteratively. The lexicographical numbers generation can also be done iteratively using a loop to simulate the DFS (by increasing and adjusting numbers without recursion), which is a good exercise in iterative thinking.
GET YOUR FREE
Coding Questions Catalog
