Lexicographical Numbers
MedPrompt
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. It leverages the fact that the lexicographical order of numbers is equivalent to the alphabetical order of their string representations. The method involves generating all numbers, converting them to strings, sorting them, and then converting them back to integers.
Algorithm
- Create a list to store the string representation of numbers from 1 to
n. - Iterate from 1 to
n, convert each integerito a string, and add it to the list. - Use a standard sorting algorithm (like
Collections.sort()in Java) to sort this list of strings lexicographically. - Create a new list of integers.
- Populate the new list by parsing the sorted strings back into integers.
- Return the final list of integers.
Walkthrough
The core idea is to transform the problem into a standard string sorting problem.
First, we generate all integers from 1 to n. For each integer, we convert it into its string equivalent. These strings are stored in a list. For example, if n=13, we would create a list of strings: ["1", "2", "3", ..., "13"].
Next, we apply a standard lexicographical sort on this list of strings. After sorting, the list for n=13 would become ["1", "10", "11", "12", "13", "2", "3", ..., "9"].
Finally, we iterate through this sorted list of strings, parse each string back into an integer, and add it to our final result list, which is then returned.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public List<Integer> lexicalOrder(int n) { // 1. Generate numbers and convert to strings List<String> stringList = new ArrayList<>(); for (int i = 1; i <= n; i++) { stringList.add(String.valueOf(i)); } // 2. Sort the list of strings lexicographically Collections.sort(stringList); // 3. Convert sorted strings back to integers List<Integer> result = new ArrayList<>(); for (String s : stringList) { result.add(Integer.parseInt(s)); } return result; }}Complexity
Time
O(N * log(N) * log10(N)). The dominant operation is sorting. Sorting N items takes O(N log N) comparisons. Each comparison between two numbers (as strings) takes time proportional to the number of digits, which is O(log10(N)).
Space
O(N * log10(N)). We need to store N strings, and the average length of these strings is proportional to the number of digits in N, which is log10(N).
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem by using built-in functionalities.
Cons
Highly inefficient in terms of time complexity due to the expensive sorting step.
Requires significant extra space to store the string representations of all numbers.
A much more efficient approach is to view the numbers as being structured in a 10-ary tree (also known as a prefix tree or trie). The numbers can then be generated in lexicographical order by performing a pre-order traversal (Depth First Search) on this conceptual tree.
Algorithm
- Initialize an empty list
result. - Loop
ifrom 1 to 9. For eachi, call a helper functiondfs(i, n, result). - The
dfs(current, n, result)function is defined as:- If
current > n, return (base case). - Add
currentto theresultlist (pre-order visit). - Loop
jfrom 0 to 9 to form child numbers. - Calculate
next = current * 10 + j. - If
next > n, break the inner loop (pruning). - Recursively call
dfs(next, n, result).
- If
- Return
result.
Walkthrough
In this model, the numbers 1 through 9 are the roots of nine distinct trees. The children of any node curr are curr*10, curr*10 + 1, ..., curr*10 + 9. A pre-order traversal naturally visits nodes in lexicographical order: parent, then children from left to right (e.g., 1, then 10, then 11...).
We implement this with a recursive dfs function. The main function initiates the DFS by calling it for each root, from 1 to 9. The dfs function first checks if the current number has exceeded n. If not, it adds the number to the result list and then recursively calls itself for all its valid children (those less than or equal to n). An important optimization is that once a child curr*10 + j exceeds n, we can stop checking subsequent siblings because they will also be greater than n.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> result = new ArrayList<>(); for (int i = 1; i <= 9; i++) { dfs(i, n, result); } return result; } private void dfs(int current, int n, List<Integer> result) { if (current > n) { return; } result.add(current); for (int i = 0; i <= 9; i++) { int next = current * 10 + i; if (next > n) { break; } dfs(next, n, result); } }}Complexity
Time
O(N). Each number from 1 to `n` is visited and processed exactly once during the DFS traversal.
Space
O(log10(N)). This is for the recursion stack. The maximum depth of the recursion is the number of digits in `n`. This does not include the O(N) space for the output list.
Trade-offs
Pros
Optimal time complexity of O(N).
The logic is elegant and directly models the hierarchical structure of lexicographical ordering.
Much more efficient than the brute-force approach.
Cons
Uses recursion, which can lead to a
StackOverflowErrorfor extremely large constraints, although this is unlikely givennis anint.Slightly higher space overhead due to the recursion stack compared to a purely iterative solution.
This approach achieves the same optimal time complexity as the DFS method but without using recursion. It iteratively calculates the next lexicographical number by simulating the pre-order traversal of the conceptual 10-ary tree. This makes it the most efficient solution in terms of both time and space.
Algorithm
- Initialize an empty list
resultand an integercurrent = 1. - Loop
ntimes to generatennumbers. - In each iteration, add
currenttoresult. - Find the next
currentnumber using the following logic:- Go Deeper: If
current * 10 <= n, updatecurrenttocurrent * 10. - Go to Sibling: Else if
current % 10 != 9andcurrent + 1 <= n, updatecurrenttocurrent + 1. - Backtrack: Otherwise, we have reached the end of a branch. Repeatedly divide
currentby 10 until its parent is not a '9' child (i.e.,(current / 10) % 10 != 9). Then, updatecurrentto its parent's next sibling:current = current / 10 + 1.
- Go Deeper: If
- Return
result.
Walkthrough
We start with current = 1 and add it to our result list. Then, in a loop that runs n times, we find the next number to add. The logic follows the pre-order traversal pattern:
- Try to go deeper: If
current * 10is within the boundn, this is our next number. This is like moving to the first child in the tree (e.g., from 1 to 10). - Try to go to the next sibling: If we can't go deeper, we try to increment
current. This is possible ifcurrentdoesn't end in 9 andcurrent + 1is still within the boundn. This is like moving to a sibling node (e.g., from 12 to 13). - Backtrack and move to the next branch: If neither of the above is possible (e.g.,
currentis 19, orcurrentis 13 whenn=13), we have exhausted a subtree. We must backtrack by moving up the tree (current /= 10) until we find an ancestor that can be incremented to start a new branch. The next number is then this ancestor's next sibling ((current / 10) + 1).
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> result = new ArrayList<>(n); int current = 1; for (int i = 0; i < n; i++) { result.add(current); if ((long)current * 10 <= n) { current *= 10; } else if (current % 10 != 9 && current + 1 <= n) { current++; } else { while ((current / 10) % 10 == 9) { current /= 10; } current = current / 10 + 1; } } return result; }}Complexity
Time
O(N). We generate each of the N numbers in the sequence. The logic to find the next number takes amortized constant time.
Space
O(1). We only use a few variables to keep track of the current number. This does not include the O(N) space required for the output list.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1) (excluding the output list).
Avoids recursion, making it robust against stack overflow issues on platforms with limited stack depth.
Cons
The logic for finding the next number can be less intuitive and more complex to implement correctly compared to the recursive DFS approach.
Solutions
Solution
class Solution { public List < Integer > lexicalOrder ( int n ) { List < Integer > ans = new ArrayList <>(); int v = 1 ; for ( int i = 0 ; i < n ; ++ i ) { ans . add ( v ); if ( v * 10 <= n ) { v *= 10 ; } else { while ( v % 10 == 9 || v + 1 > n ) { v /= 10 ; } ++ v ; } } return ans ; } }/** * @param {number} n * @return {number[]} */ var lexicalOrder = function ( n ) { let ans = []; function dfs ( u ) { if ( u > n ) { return ; } ans . push ( u ); for ( let i = 0 ; i < 10 ; ++ i ) { dfs ( u * 10 + i ); } } for ( let i = 1 ; i < 10 ; ++ i ) { dfs ( i ); } return ans ; };class Solution { public: vector < int > lexicalOrder ( int n ) { vector < int > ans ; int v = 1 ; for ( int i = 0 ; i < n ; ++ i ) { ans . push_back ( v ); if ( v * 10 <= n ) v *= 10 ; else { while ( v % 10 == 9 || v + 1 > n ) v /= 10 ; ++ v ; } } return ans ; } };class Solution : def lexicalOrder ( self , n : int ) -> List [ int ]: v = 1 ans = [] for i in range ( n ): ans . append ( v ) if v * 10 <= n : v *= 10 else : while v % 10 == 9 or v + 1 > n : v //= 10 v += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.