Check Whether a Stack Is Empty After Each Operation

Easy5 min

Topics

BasicsStack

Companies

TCSInfosysWipro

Process ops on an initially empty stack: a positive number means push it, and 0 means pop (ignored if the stack is empty). After every operation, record 1 if the stack is empty and 0 if it is not. isEmpty is the guard behind every safe pop and peek. This problem also shows a useful habit: notice which information a question really needs. Emptiness depends only on how many items are on the stack, so a single counter can replace the stack itself.

Test Case 1:

Input:ops = [7, 0, 0, 3, 8, 0]

Output:[0, 1, 1, 0, 0, 0]

Explanation:Empty (1) only after the first pop and the ignored second pop; otherwise something is on the stack (0).

Test Case 2:

Input:ops = [0, 0]

Output:[1, 1]

Explanation:Popping an empty stack leaves it empty.

Constraints

◆1 ≤ ops.length ≤ 1000
◆0 ≤ ops[i] ≤ 1000000 (a positive value means push it, 0 means pop)

Try the Dry Run

Mode

Approach

Approach & Solutions

Keep a Real StackGood

Store the pushed values in an actual stack, pop when asked (never from an empty stack), and after each operation record 1 if the stack's isEmpty check is true and 0 otherwise.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] emptyAfterEach(int[] ops) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[ops.length];
        for (int i = 0; i < ops.length; i++) {
            if (ops[i] > 0) {
                stack.push(ops[i]);
            } else if (!stack.isEmpty()) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 1 : 0;
        }
        return result;
    }
}

Only Track the SizeOptimal

Emptiness depends only on how many items are on the stack, not on their values. So keep a size counter instead of a real stack: push adds one, a pop on a non-empty stack subtracts one, and the stack is empty exactly when size is 0.