Implement a Stack Using a Resizable Array

Easy15–20 min

Topics

StackArrayDesign

Companies

AmazonMicrosoftAdobe

Implement a LIFO stack backed by a plain array, supporting push(v), pop(), top(), isEmpty(), and size(). To make this testable with a single function call, this version takes a fixed sequence of operations (each with an argument, ignored when the operation doesn't need one) and replays them in order, returning the result of every pop, top, isEmpty, and size call as an array (push has no return value in a real stack API). An array-backed stack is simple: push and pop both touch only the last occupied slot. The interesting part is what happens when the array runs out of room. Growing it by a fixed amount (say, one slot) every time keeps the logic simple but means nearly every push pays for a full copy of everything already stored — O(n²) total work across n pushes. Doubling the capacity instead trades a little extra unused memory for a dramatic speedup: resizes become exponentially rarer, so the total copying work across n pushes drops to O(n), making every push O(1) on average — this "spread the occasional expensive operation across many cheap ones" trick is called amortized analysis.

Test Case 1:

Input:ops = [push, push, push, pop, pop, top], args = [5, 10, 15, -, -, -]

Output:[15, 10, 5]

Explanation:push 5, 10, 15 onto the stack; pop returns 15 (last in), pop returns 10, top peeks at 5 without removing it.

Test Case 2:

Input:ops = [isEmpty, push, isEmpty, pop, isEmpty], args = [-, 7, -, -, -]

Output:[1, 0, 7, 1]

Explanation:Starts empty (isEmpty→1). After push(7) it's non-empty (isEmpty→0). pop removes and returns 7. Now it's empty again (isEmpty→1).

Test Case 3:

Input:ops = [push, push, size, pop, size], args = [1, 2, -, -, -]

Output:[2, 2, 1]

Explanation:After two pushes, size→2. pop removes the top (2) and returns it. size→1 afterward.

Constraints

◆1 ≤ number of operations ≤ 12
◆Each operation is one of push, pop, top, isEmpty, or size
◆0 ≤ pushed value ≤ 1000
◆pop and top return -1 when the stack is empty
◆This version replays a fixed sequence of operations and reports the result of every pop, top, isEmpty, and size call, in order (push has no return value)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Grow the Backing Array by One Slot at a Time

Brute

Back the stack with a plain array that starts at capacity 1. Whenever a push arrives and the array is already full, grow it by exactly one slot: allocate a new array one element larger, copy everything over, then write the new value. pop, top, isEmpty, and size are all trivial O(1) reads from the end. But growing by only one slot means nearly every push (after the first) pays for a full copy of everything pushed so far — n pushes cost O(1 + 2 + 3 + ... + n) = O(n²) total copying work.

TimeO(n) worst case per push

SpaceO(n)

Java

Try it out

class Solution {
    public int[] stackOpsArray(String[] ops, int[] args) {
        int[] arr = new int[1];
        int size = 0;
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < ops.length; i++) {
            String op = ops[i];
            if (op.equals("push")) {
                if (size == arr.length) {
                    int[] grown = new int[arr.length + 1];
                    for (int k = 0; k < size; k++) grown[k] = arr[k];
                    arr = grown;
                }
                arr[size++] = args[i];
            } else if (op.equals("pop")) {
                results.add(size == 0 ? -1 : arr[--size]);
            } else if (op.equals("top")) {
                results.add(size == 0 ? -1 : arr[size - 1]);
            } else if (op.equals("isEmpty")) {
                results.add(size == 0 ? 1 : 0);
            } else {
                results.add(size);
            }
        }
        int[] output = new int[results.size()];
        for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
        return output;
    }
}

Optimal — Double the Capacity Instead of Growing by One

Optimal

Same array-backed idea, but whenever more room is needed, double the capacity (1 → 2 → 4 → 8 ...) instead of growing it by one slot. Most pushes now land in free space that's already waiting, costing O(1); a resize still copies everything, but it happens exponentially less often, so the total copying work across n pushes is only O(n) overall — each element gets copied at most a constant number of extra times before the array comfortably fits everything. pop, top, isEmpty, and size stay the same O(1) reads.

TimeO(1) amortized per push