Problem Explanation

We are given an integer n and the task is to return the list of numbers from 1 to n in the lexicographical order. The lexicographical order is a generalization of the alphabetical order to sequences of ordered symbols or, more generally, of elements of a totally ordered set.

For example, if given 13, the output would be [1,10,11,12,13,2,3,4,5,6,7,8,9].

The problem here is that the numbers are not in the order that we usually follow, i.e., ascending or descending, but instead they are in the lexicographical order.

Approach

Here, we can solve the problem using the Depth-first search (DFS) algorithmic concept. The idea is to put each number in each digit from low to high. Take 15 as an example:

Start from 1 (1st level), then 10 (2nd level), then 100 (3rd level). But for 100, we can not append 1000 (4th level) to result, since 1000 is larger than 15. Also, we can not append 101, since 1 (in the 3rd level) is not the previous level of 101 (in the 4th level). Then we continue to traverse the 2nd level, i.e., still at "1" in the 2nd level. Hence we increment "1" to "2" and get "11", and append "11" to result. We fail to continue to increment "1" to "2", since "12" is larger than "15". Hence we move to next iteration.

The process above is actually a Depth-first search traversal of an n-ary tree.

Example

Let's try an example: n=13

1 -> 10 -> 11 -> 12 -> 13 -> (backtrack to the root, trying to add 14 -> 140) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

So we get the output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Now, let's dig into the code of each language with explanation.

Python Solution

1
2python
3class Solution:
4    def lexicalOrder(self, n: int) -> List[int]:
5        # list to store result
6        res = []
7
8        def dfs(n, curr):
9            if curr > n:
10                return
11            res.append(curr)
12            for i in range(10):
13                if 10*curr + i > n:
14                    return
15                dfs(n, 10*curr + i)
16
17        for i in range(1, 10):
18            dfs(n, i)
19        return res

In the python solution, a helper function dfs is defined to loop through all the numbers in the lexicographical order. It starts from the curr and ends when the current number becomes larger than n.

Java Solution

1
2java
3class Solution {
4    public List<Integer> lexicalOrder(int n) {
5        List<Integer> res = new ArrayList<>();
6        for (int i = 1; i < 10; ++i) {
7            dfs(i, n, res);
8        }
9        return res;
10    }
11
12    void dfs(int curr, int n, List<Integer> res) {
13        if (curr > n) return;
14        res.add(curr);
15        for (int i = 0; i < 10; ++i) {
16            if (10 * curr + i > n) return;
17            dfs(10 * curr + i, n, res);
18        }
19    }
20}

In Java, similar to python code we define a helper function dfs. The function performs a depth first search through the number space starting from the curr till n.

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<int> lexicalOrder(int n) {
6        vector<int> res;
7        for(int i=1;i<10;++i)
8            dfs(i,n,res);
9        return res;
10    }
11    void dfs(int curr, int n, vector<int>& res){
12        if(curr>n)
13            return;
14        else{
15            res.push_back(curr);
16            for(int i=0;i<10;++i){
17                if(10*curr+i>n)
18                    return;
19                dfs(10*curr+i,n,res);
20            }
21       }
22    }
23};

The C++ solution is a replica of the Java solution. It also follows the same depth-first search approach, where it iteratively dives into the number space and backtracks when needed.

JavaScript Solution

1
2javascript
3var lexicalOrder = function(n) {
4    var res = [];
5    for (var i=1; i<10; ++i)
6        dfs(i, n, res);
7    return res;
8};
9
10var dfs = function(curr, n, res){
11    if (curr>n)
12        return;
13    else{
14        res.push(curr);
15        for(var i=0;i<10;++i){
16            if( 10*curr+i>n)
17                return;
18            dfs(10*curr+i, n, res);
19        }
20    }
21}

In the JavaScript solution, similar to our python code we define a helper function dfs. The function iteratively selects each number in the range from 1 to n, in lexicographical order and appends them in the result array.

C# Solution

1
2csharp
3public class Solution {
4    public IList<int> LexicalOrder(int n) {
5        List<int> res = new List<int>();
6        for (int i = 1; i < 10; ++i) {
7            dfs(i, n, res);
8        }
9        return res;
10    }
11    
12    void dfs(int curr, int n, List<int> res) {
13        if (curr > n) return;
14        res.Add(curr);
15        for (int i = 0; i < 10; ++i) {
16            if (10 * curr + i > n) return;
17            dfs(10 * curr + i, n, res);
18        }
19    }
20}

In the C# solution, we add the numbers in lexicographical order to the list res using the Depth-first search (DFS) approach. Same like our other language solutions, we start from 1 and end at n.# Ruby Solution

The Ruby solution is indeed a little different from the rest of the solutions as it implements a range to create a list of number from 1 to n.

1
2ruby
3def lexical_order(n)
4  (1..n).to_a.sort_by(&:to_s)
5end

In the Ruby solution, we create a range from 1 to ‘n’ and convert it to an array using the to_a method. The sort_by method helps to sort the array in the lexicographical order of their string representations.

Analysis

The algorithm used here, i.e., DFS, is a powerful one – it lets us traverse an entire space in a flexible order. As in each DFS step we have to loop through 10 digits, and for each digit we DFS through new number by adding the current digit to the end of the previous number. So the time complexity would be O(n).

This is one way of solving this problem, surely we could find other ways as well. But the essence here is to find a well-ordered path to all numbers less than n (both included), and DFS is a method quite suited for that.

In conclusion, we have seen how each major programming language can solve this problem in a similar way using iterative loops and depth-first search strategy. This depth-first search strategy is a highly recommended strategy especially when dealing with large datasets as it covers all possibilities. And of course, it is worth noting that the specific implementation of the solution can vary slightly depending on the language and its features.