LeetCode: 386. Lexicographical Numbers

386. Lexicographical Numbers  QuestionEditorial Solution  My Submissions
Total Accepted: 4021
Total Submissions: 12734
Difficulty: Medium
Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

class Solution {
public:

    vector<int> lexicalOrder(int n) {
        vector<int> res;
        
        int candidate = 1;
        int count = 0;
        
        while (count < n) {
            res.push_back(candidate);
            ++count;
            if (10 * candidate <= n) {
                candidate *= 10;
            } else if (candidate + 1 <= n) {
                candidate++;
                while (candidate % 10 == 0) candidate = candidate / 10;
            } else {
                candidate = candidate / 10;
                while ((candidate + 1) % 10 == 0) candidate = candidate / 10;
                ++candidate;
            }
        }
        return res;
    }
};