Lexicographical Numbers Leetcode Solution


Difficulty Level Medium
Frequently asked in ByteDance
Depth First Search

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.

Implementation

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++)
           ans.add( Integer.parseInt(a[i-1]));
       
        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.

Lexicographical Numbers Leetcode Solution

Implementation

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{
            res.add(cur);
            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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions