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.
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 ; } }Video 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.