Last updated on February 2nd, 2025 at 06:29 am

Here, we see a Lexicographical Numbers LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth First Search, Tree

Companies

Bloomberg

Level of Question

Medium

Lexicographical Numbers LeetCode Solution

1. Problem Statement

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]

2. Coding Pattern Used in Solution

The coding pattern used in this code are Tree Depth-First Search (DFS): The recursive function explores all possible numbers in a tree-like structure where each node represents a number, and its children represent numbers formed by appending digits and Sorting: The approach relies on sorting the numbers as strings to achieve lexicographical order.

3. Code Implementation in Different Languages

3.1 Lexicographical Numbers C++

class Solution {
public:
    void solve(int i, int n,vector<int> &v){
        if(i>n) return;
        v.push_back(i);
        for(int j=0;j<=9;j++){
            solve(i*10+j,n,v);
        }
    }
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        for(int i=1;i<10;i++){
            solve(i,n,ans);
        }
        return ans;
    }
};

3.2 Lexicographical Numbers Java

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        String[] str = new String[n];
        for(int i=1;i<=n;i++) str[i-1] = Integer.toString(i);
        Arrays.sort(str);
        for(String s: str) list.add(Integer.parseInt(s));
        return list;        
    }
}

3.3 Lexicographical Numbers JavaScript

var lexicalOrder = function(n) {
    const a = new Array(n)
    for(let i = 0; i < n; i++){
        a[i] = i + 1;
    }
    return a.sort()    
};

3.4 Lexicographical Numbers Python

class Solution(object):
    def lexicalOrder(self, n):
        top = 1
        while top * 10 <= n:
            top *= 10
        def mycmp(a, b, top=top):
            while a < top: a *= 10
            while b < top: b *= 10
            return -1 if a < b else b < a
        return sorted(xrange(1, n+1), mycmp)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(log⁡n)
Java	O(n⋅log⁡n)	O(n)
JavaScript	O(n⋅log⁡n)	O(n)
Python	O(n⋅log⁡n)	O(n)