Fast-Push Java Solution


  • 0
    G

    O(1) for push()
    O(2n) for pop() and peek()

    class MyQueue {
        Stack<Integer> in = new Stack<>();
        Stack<Integer> off = new Stack<>();
        
        // Push element x to the back of queue.
        public void push(int x) {
            in.add(x);
        }
    
        /**
         * Removes the element from in front of queue.
         * 
         * (1) Elements from `in` are popped onto `off`,
         *     thus reversing the stack.
         * (2) The top element is popped from `off`, which
         *     was our bottom element from `in`
         * (3) Elements from `off` are popped onto `in`,
         *     thus re-reversing the stack and maintaining
         *     our invariant (except first-in was popped).
         */
        public void pop() {
            while (!in.empty()) {
                off.add(in.pop());
            }
            off.pop();
            while (!off.empty()) {
                in.add(off.pop());
            }
        }
    
        /**
         * Get the front element.
         * 
         * (1) Elements from `in` are popped onto `off`,
         *     thus reversing the stack.
         * (2) The top element from `off` is stored in `ans`.
         *     This was our bottom element from `in`.
         * (3) Elements from `off` are popped onto `in`,
         *     thus re-reversing the stack and maintaining
         *     our invariant.
         */
        public int peek() {
            while (!in.empty()) {
                off.add(in.pop());
            }
            int ans = off.peek();
            while (!off.empty()) {
                in.add(off.pop());
            }
            return ans;
        }
    
        // Return whether the queue is empty.
        public boolean empty() {
            return in.empty();
        }
    }```

  • 0
    G

    The above code scored better than ~91% of submissions, however, the far-cleverer solution at https://discuss.leetcode.com/topic/17974/short-o-1-amortized-c-java-ruby scores better than only ~50%.

    It seems like the grader is penalizing amortization? Or am I missing something?


Log in to reply
 

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