Leetcode Lexicographical Number problem solution

YASH PAL,

In this Leetcode Lexicographical Number problem solution you have 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.

Leetcode Lexicographical Number problem solution

Problem solution in Python.

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        l = list()
        for i in range(1,n+1):
            l.append(str(i))
        l.sort()
        i = len(l)-1
        while i>0:
            l[i] = int(l[i])
            i-=1
        l[i] = int(l[i])
        return l

Problem solution in Java.

public List<Integer> lexicalOrder(int n) {
        int num = 1;
        List<Integer> results = new ArrayList<>();
        while (true) {
            if (num <= n) {
                results.add(num);
                num *= 10;
                continue;
            }
            
            num /= 10;
            while (num % 10 == 9 && num != 0)
                num /= 10;
            if (num == 0)
                return results;
            num += 1;
        }
    }

Problem solution in C++.

class Solution {
    int next(int last, int n)
    {
        if (last * 10 <= n)
            return last * 10;
        if (last == n)
            last /= 10;
        ++last;
        while(last % 10 == 0)
            last /= 10;
        return last;
    }
public:
    vector<int> lexicalOrder(int n) {
        if (n < 1) return vector<int>();
        vector<int> result(n);
        result[0] = 1;
        for (int i = 1; i < n; ++ i)
            result[i] = next(result[i - 1], n);
        return result;
    }
};

coding problems