Java very easy understanding iterative solution, O(n) time and O(1) space


  • 1
    P

    Lets assume n=115, I just count from 1 to 10, 100 until 1000 which is larger than 115, then add one to the previous one which is 100, so it's 101. A corner case is that when we reach 9 such as 109, we need to count back to 11 before 110 which is the (x+1)%10==0 part. Continue doing this until the size of list reaches n. Overall, the time is 220ms.

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res=new ArrayList<>();
            int x=0;
            while(res.size()<n ){
                x++;
                while(x<=n){
                    if(res.size()==n) return res;
                    res.add(x);
                    x=x*10;
                }
                x=x/10;
                while((x+1)%10==0){
                    x=(x+1)/10-1;
                }
            }
            
            return res;
        }
    }
    

Log in to reply
 

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