Lexicographical Numbers

Problem

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.

Solution

Basic Iteration: O(n) time O(1) space

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        int cur = 1;
        for (int i = 1; i <= n; i++) {
            res.add(cur);
            if (cur * 10 <= n) cur *= 10; //after 45 is 450 if not exceed 
            else if (cur % 10 != 9 && cur + 1 <= n) cur++; //after 45 is 46 if 450 exceed 
            else {
                //after 499 is 5, which becomes smaller so we don't need to check exceed 
                while (cur / 10 % 10 == 9) cur /= 10;
                cur = cur / 10 + 1; //because of this line, the previous check is "cur / 10 % 10 == 9"
            }
        }
        return res;
    }
}

Analysis

We use a for loop which will execute exactly n times
Inside the loop, we first add the cur to our res
Then we need to figure out what is the next valid number
We divide into three situations and comments explain each situation