Java O(n) time, O(1) space iterative solution 130ms


  • 128
    S
    public List<Integer> lexicalOrder(int n) {
            List<Integer> list = new ArrayList<>(n);
            int curr = 1;
            for (int i = 1; i <= n; i++) {
                list.add(curr);
                if (curr * 10 <= n) {
                    curr *= 10;
                } else if (curr % 10 != 9 && curr + 1 <= n) {
                    curr++;
                } else {
                    while ((curr / 10) % 10 == 9) {
                        curr /= 10;
                    }
                    curr = curr / 10 + 1;
                }
            }
            return list;
        }
    

    The basic idea is to find the next number to add.
    Take 45 for example: if the current number is 45, the next one will be 450 (450 == 45 * 10)(if 450 <= n), or 46 (46 == 45 + 1) (if 46 <= n) or 5 (5 == 45 / 10 + 1)(5 is less than 45 so it is for sure less than n).
    We should also consider n = 600, and the current number = 499, the next number is 5 because there are all "9"s after "4" in "499" so we should divide 499 by 10 until the last digit is not "9".
    It is like a tree, and we are easy to get a sibling, a left most child and the parent of any node.


  • 0
    J

    best solution!


  • 15
    G

    really smart solution, so far best.
    The only challenge here these observations are not very straightforward, likely without some fresh memorization I will forget this solution during interview. I still recommend DFS solution though since I could visualize the solution which really helps memorize it.


  • 2
    S

    @GoCodeZ
    It is actually a tree with dfs method, but only we can get the next node easier:)


  • 0
    F
    This post is deleted!

  • 8
    I

    @songzec Similar idea, but less "/10", and did not waste the n+1th calculation.

    /*
     * ans[i] = ans[i-1]*10 <= n ? ans[i-1]*10 : ans[i-1]%10 < 9 ? ans[i-1] + 1 : ans[i-1]/10%10 < 9 ? ...
     */
    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> ans = new ArrayList<>(n);
            ans.add(1);
            for (int i = 1, prev = 1; i < n; ++i) {
                if (prev * 10 <= n) {
                    prev *= 10;
                } else {
                    while (prev % 10 == 9 || prev == n) prev /= 10;
                    prev++;
                }
                ans.add(prev);
            }
            return ans;
        }
    }
    

  • 0
    W

    similar idea, a little cleaner

    class Solution(object):
        def lexicalOrder(self, n):
            """
            :type n: int
            :rtype: List[int]
            """
            res = []
            curr = 1
            for _ in xrange(n):
                res.append(curr)
                if curr*10 <= n:
                    curr = curr*10
                else:
                    if curr%10 != 9 and curr + 1 <= n:
                        curr = curr + 1
                    else:
                        # look back to find the digit that needs to be incremented
                        curr = curr/10
                        while (curr%10) == 9:
                            curr = curr/10
                        
                        curr = curr + 1
                
            return res
    

  • 1
    H
    vector<int> lexicalOrder(int n) {
    vector<int> res;
    int cur = 1;
    while (res.size() < n) {
    	res.push_back(cur);
    	if (cur * 10 <= n) {
    		cur *= 10;
    	}
    	else if (cur % 10 == 9 ||cur==n) {
    		while ((cur % 10 == 9) || cur == n) {
    			cur /= 10;
    		}
    		cur += 1;
    	}
    	else if(cur<n) cur++;
    }
    return res;
    

    }


  • 0
    Y

    Best solution! Thanks.


  • 0
    D
    else {
                    while ((curr / 10) % 10 == 9) {
                        curr /= 10;
                    }
                    curr = curr / 10 + 1;
                }
    

    Could you please explain this case ?

    Thanks.


  • 2
    S

    @dreamer92
    Consider case: curr = 4999, n = 10000, in this case the next one should be 5. And this is how I get it.


  • 0
    G

    Heya I'm getting memory limit exceeded when I use this solution, any ideas why?


  • 2
    M

    I make a little modification that is a litter simpler in your 3rd "if" branch.

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            int cur = 1;
            List<Integer> res = new LinkedList<Integer>();
            for(int i = 0; i < n; i++){
                res.add(cur);
                if(cur * 10 <= n){
                    cur *= 10; 
                }else if(cur % 10 != 9 && cur + 1 <= n){
                    cur++;
                }else{
                    cur = cur / 10;
                    while(cur % 10 == 9){
                        cur = cur / 10;
                    }
                    cur++;
                }
            }
            return res;
        }
    }

  • 0
    Z

    Cool implementation, but there is no way to make it O(1) space, because answer already requires O(n) space


  • 0
    S

    @ZhassanB I think when we say O(1) space we usually mean O(1) extra space.


  • 2
    L

    @iambright Like it. Make it shorter:

    public List<Integer> lexicalOrder(int n) {
            List<Integer> ans = new ArrayList<>(n);
            for (int i = 1, curr = 1; i <= n; ++i) {
            	ans.add(curr);
                if (curr * 10 <= n) {
                    curr *= 10;
                } else {
                    while (curr % 10 == 9 || curr == n) curr /= 10;
                    curr++;
                }
                
            }
            return ans;  
        }
    

  • 0
    Y

    Ur idea is rewrite the recursion method into iteration, thx for the code~~lol


  • 0
    Y

    Similar idea, but compares to 10, not 9

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<Integer>();
            int num = 1;
            for (int i=0; i<n; i++) {
                res.add(num);
                if (num * 10 <= n) {
                    num *= 10;
                } else if (num + 1 <= n || (num + 1) % 10 == 0) {
                    num++;
                    while (num % 10 == 0) num /= 10;
                } else {
                    num = num / 10 + 1;
                }
            }
            return res;
        }
    }
    

  • 0

    @iaming

    Hats off. So carefully tailored and trimmed.


  • 0

    Best solution! So clever!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.