In this post, we are going to solve the 386. Lexicographical Numbers problem of Leetcode. This problem 386. Lexicographical Numbers is a Leetcode medium level problem. Let’s see the code, 386. Lexicographical Numbers – Leetcode Solution.

Problem

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Example 1 :

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2 :

Input: n = 2
Output: [1,2]

Constraints

• 1 <= n <= 5 * 104

Now, let’s see the code of 386. Lexicographical Numbers – Leetcode Solution.

Lexicographical Numbers – Leetcode Solution

386. Lexicographical Numbers – Solution in Java

class Solution {
    
    public void helper(int i, int n, List<Integer> ans){
        if(i>n)return;
        ans.add(i);
        for(int j=0;j<10;j++){
            helper(10*i+j,n,ans);
        }
                
    }
    
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<Integer>();
        for(int i=1;i<=9;i++){
             helper(i,n,ans);
        }
       
        return ans;
    }
}

386. Lexicographical Numbers – Solution in C++

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i=1;i<10;++i){
          dfs(i, n, res); 
        }
        return res;
    }
    
    public 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);
            }
        }
    }
}

386. Lexicographical Numbers – Solution in Python

    def lexicalOrder(self, n):
        def dfs(k, res):
            if k <= n:
                res.append(k)
                t = 10*k
                if t <= n:
                    for i in range(10):
                        dfs(t + i, res)
        res = []
        for i in range(1, 10):
            dfs(i, res)
        return res

Note: This problem 386. Lexicographical Numbers is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.