iterative solution for Problem 386, O(n) time and O(1) space


  • 0
    F

    First, by several special cases, I learned that the numbers in the lexicographical order were generated by multiplying 10. But if the value after the multiplication is larger than the target value, then it's divided by 10 and incremented by 1 at first, before it's multiplied by 10. This is like dfs, only now multiplication is stack pushing, while division is stack popping.

    The code below is the implementation of the idea above. But I am sure there is a better implementation, because in this code, every time I encounter a leaf node,I go one more step deeper to get a 'null node'(conceptually), and then step backwards and switch to another branch. I am sure there is a way to avoid visiting the null node in the first place.

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> nums = new ArrayList<>();
            
            if(n >= 1) {
                int stackTop = 1;
                int stackSize = 1;
                
                while(stackSize > 0) {
                    if(stackTop > n) {
                        stackSize--;
                        stackTop /= 10;
                        while(stackSize>0 && stackTop%10 == 9) {
                            stackSize--;
                            stackTop /= 10;
                        }
                        stackTop++;
                    } else {
                        nums.add(stackTop);
                        stackTop *= 10;
                        stackSize++;
                    }
                }
            }
            
            return nums;
        }
    }
    

Log in to reply
 

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