# Lexicographical Numbers Leetcode Solution

Difficulty Level Medium
algorithms coding Depth First Search Interview interviewprep LeetCode LeetCodeSolutionsViews 2457

## Problem statement

In the problem ” Lexicographical Numbers” we are given a number n. Our task is to print numbers between 1 and n in lexicographical order.

### Example

`n=13`
`[1 10 11 12 13 2 3 4 5 6 7 8 9]`

Explanation: As we have to print numbers between 1-13 in lexicographical order, the numbers are  [1 10 11 12 13 2 3 4 5 6 7 8 9].

## Brute Force Approach for Lexicographical Numbers Leetcode Solution

The brute force approach to solve the problem is as follows:

1. Convert all the positive integer numbers between 1 to n into strings.
2. Now, sort the strings. This will arrange the numbers in lexicographical order.
3. Now convert the sorted strings into integers again and this will give the result.

### C++ code for Lexicographical Numbers

```#include <bits/stdc++.h>
using namespace std;
vector<int> lexicalOrder(int n) {
string a[n];
for(int i=1;i<=n;i++)
a[i-1]=to_string(i);
sort(a,a+n);
vector<int>ans;
for(int i=1;i<=n;i++)
ans.push_back(stoi(a[i-1]));
return ans;
}
int main()
{
int n=13;
vector<int> ans=lexicalOrder(n);
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
return 0;
}```
`[1 10 11 12 13 2 3 4 5 6 7 8 9]`

### Java code for Lexicographical Numbers

```import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*;
public class Tutorialcup {
public static List<Integer> lexicalOrder(int n) {
String[] a = new String[n];
for(int i=1;i<=n;i++)
a[i-1]=Integer.toString(i);
Arrays.sort(a);
List<Integer> ans=new ArrayList<Integer>();
for(int i=1;i<=n;i++)

return ans;
}
public static void main(String[] args) {
int n=13;
List<Integer> ans = new ArrayList<>(n);
ans=lexicalOrder(n);
System.out.println(Arrays.toString(ans.toArray()));
}
}```
```[1 10 11 12 13 2 3 4 5 6 7 8 9]
```

## Complexity Analysis of Lexicographical Numbers Leetcode Solution

### Time complexity

The time complexity of the above code is O(nlogn) because we are sorting the strings with n string. Here n is the given number.

### Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

## DFS Approach for Lexicographical Numbers Leetcode Solution

The idea is pretty simple. Every time we start with a single digit from 1-9 and then keep on adding digits from 0-9 on those numbers as long as it is smaller than n. So this is exactly the same as the Depth-First-Search algorithm.

So we will start with 1 and will perform DFS for it as long as it is smaller or equal to n.

We will repeat these for all digits till 9 then store and print the DFS result.

### C++ code for Lexicographical Numbers

```#include <bits/stdc++.h>
using namespace std;
void dfs(int cur, int n, std::vector<int>& ret)
{
if (cur <= n)
{
ret.push_back(cur);
for (int i = 0; i <= 9; ++i)
{
dfs(cur*10+i, n, ret);
}
}
}
vector<int> lexicalOrder(int n) {
vector<int> ret;
for (int i = 1; i <= 9; ++i)
{
dfs(i, n, ret);
}
return ret;

}

int main()
{
int n=13;
vector<int> ans=lexicalOrder(n);
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
return 0;
}```
`[1 10 11 12 13 2 3 4 5 6 7 8 9]`

### Java code for Lexicographical Numbers

```import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*;
public class Tutorialcup {
public static List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
for(int i=1;i<10;++i){
dfs(i, n, res);
}
return res;
}

public static void dfs(int cur, int n, List<Integer> res){
if(cur>n)
return;
else{
for(int i=0;i<10;++i){
if(10*cur+i>n)
return;
dfs(10*cur+i, n, res);
}
}
}
public static void main(String[] args) {
int n=13;
List<Integer> ans = new ArrayList<>(n);
ans=lexicalOrder(n);
System.out.println(Arrays.toString(ans.toArray()));
}
}```
```[1 10 11 12 13 2 3 4 5 6 7 8 9]
```

## Complexity Analysis of Lexicographical Numbers Leetcode Solution

### Time complexity

The time complexity of the above code is O(n) because we are traversing the elements only once. Here n is the given value.

### Space complexity

The space complexity of the above code is O(log(h)) because we are using DFS. Here h is the height of the DFS tree.

References

Translate »