DSA sheet · Stack · Concept video

Stack Patterns Overview

This is the opening video of the stack topic. It answers two questions, what is a stack and why do we need one when we already have arrays, and then walks through the six patterns that the teacher says cover about 90–95% of the stack questions you'll meet in interviews and online tests. No single problem is solved fully here. Instead, every pattern gets its idea, a tiny worked example, and the reason a stack beats the plain-array approach. This page adds a ready-to-use Python template for each pattern, so you can come back here before solving any problem in the sheet.

This concept page follows its own order:
① what a stack is → ② why we need it / how to spot a stack problem → ③ each pattern: idea → tiny example → why not an array → Python template → ④ which sheet problems belong to which pattern → ⑤ remember

• Part 0 · What a stack is
• Part A · Why we need a stack, and how to spot a stack problem
• Part B · Pattern 1: Monotonic stack
• Part C · Pattern 2: Expression evaluation
• Part D · Pattern 3: Undo (cancel the previous item)
• Part E · Pattern 4: Parentheses
• Part F · Pattern 5: Stack-based design
• Part G · Pattern 6: Recursive stack
• Part H · Which sheet problem uses which pattern
• Part I · Revision page

Part 0 · What a stack is

1A linear structure without indexing

Like an array, a stack is linear: items sit one after another in a line. The big difference: an array lets you jump to any position with an index (arr[2]). A stack has no indexing. You may only work at one end, called the top.

Three operations are allowed, all at the top:

2Watch it work: push 1, 2, 4, 5

Take the items 1, 2, 4, 5 and push them one by one. Each new item lands on top of the previous one:

Now suppose you want to remove 2. You can't reach in and grab it. Only the top can be popped: first 5, then 4, and only then is 2 on top and poppable. The item that went in last comes out first. This rule is called LIFO (Last In, First Out).

3Python habits used in every page of this notebook

st = []            # empty stack
st.append(1)       # push -> [1]
st.append(2)       # push -> [1, 2]   (left = bottom, right = top)
top = st[-1]       # peek -> 2
x = st.pop()       # pop  -> x = 2, st = [1]
if st:             # ALWAYS check before pop / peek
    st.pop()
print(st)          # []

Part A · Why we need a stack, and how to spot a stack problem

1The problem with arrays: looking back costs a second loop

Say you're walking through an array [1, 2, 3, …] and you've reached 3. Now the question wants something about the items before 3 (like 2 or 1). With a plain array you must start a second loop that walks backwards from 3. Doing that from every position is a loop inside a loop → O(n²).

2What the stack does instead

As we walk forward, we keep the earlier items that still matter (for example, the biggest or smallest ones so far, whatever the question needs) in a stack. When we need to "look back", the right item is waiting on top, with no backward loop. One pass → O(n).

The price is memory: the stack can hold up to n items, so O(n) extra space. A stack is the right tool when that extra space is allowed.

3How to spot a stack problem

Part B · Pattern 1: Monotonic stack

1The idea

Monotonic means "always moving in one direction". A monotonic stack is an ordinary stack where we make sure the items inside are always sorted, either increasing or decreasing from bottom to top.

A normal stack would simply hold everything we push. A monotonic stack, before pushing a new item, pops every item on top that would break the order. Those popped items are ones we have proved useless for the rest of the problem.

2Tiny example: push 2, 4, 3, 8, 1

A normal stack ends as [2, 4, 3, 8, 1], with no order at all. Here is what the two monotonic kinds keep:

At every row, each stack is sorted. That's the whole definition.

3Why it's useful (what the stack remembers)

Take "next greater element": for every item, find the first bigger item to its right. Walk from the right and keep a decreasing stack (bottom → top). When a new item x arrives, every smaller-or-equal item on top gets popped. Why is that safe? Any item further left looks right and sees x first, and x is at least as big, so a popped item can never be the first bigger one for anybody again. What survives on top is exactly the answer for x.

The teacher says about 25–30% of stack questions belong to this pattern (next greater element, next smaller element, daily temperatures, …). She leaves the "how to maintain it in code" for the problem videos. Problems 2–4 of this notebook cover it in full.

4Why not an array?

Without the stack, for every item you'd scan right until you find a bigger one: O(n²). With the stack, every item is pushed once and popped at most once: O(n).

5Python template

def next_greater(arr):
    ans = [-1] * len(arr)
    st = []                                  # bottom -> top: strictly decreasing values
    for i in range(len(arr) - 1, -1, -1):    # answer is on the right -> walk from the right
        while st and st[-1] <= arr[i]:       # not greater -> useless forever
            st.pop()
        if st:
            ans[i] = st[-1]                  # survivor on top = first greater on the right
        st.append(arr[i])
    return ans

Part C · Pattern 2: Expression evaluation

1The idea

When the input contains numbers and operators (+, −, ×, ÷) and you must calculate the result, think stack. The reason is precedence: by the BODMAS rule, × and ÷ must happen before + and −. So you often can't apply an operator the moment you see it. You have to keep earlier numbers waiting somewhere and come back to them. Keeping things waiting is what a stack is for.

2Tiny example: 2 + 3 * 5 - 4

• Correct (BODMAS): 3 × 5 = 15 first, then 2 + 15 − 4 = 13.
• Wrong (just left to right): 2 + 3 = 5, × 5 = 25, − 4 = 21.

To get 13, we evaluate 3 × 5 and only then go back left to add the 2. "Going back left" with plain arrays means nested loops (O(n²)). The stack avoids that.

3The stack method (three things to track)

The teacher keeps track of three things: the pointer i that walks the string, the last operator seen (op), and the stack of numbers. The rule when a number is complete:

At the end, the answer = sum of everything in the stack.

Hand table for 2+3*5-4

Sum = 2 + 15 − 4 = 13 ✓

4Python template

def calculate(s):
    st = []
    num = 0
    op = '+'                                 # pretend there is a '+' before the first number
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)         # numbers can have many digits
        if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
            if op == '+':
                st.append(num)
            elif op == '-':
                st.append(-num)
            elif op == '*':
                st.append(st.pop() * num)
            else:                            # '/': cut toward zero
                a = st.pop()
                q = abs(a) // num
                st.append(q if a >= 0 else -q)
            op = ch                          # remember this operator for the NEXT number
            num = 0
    return sum(st)

Part D · Pattern 3: Undo (cancel the previous item)

1The idea

Some questions say: "when you meet a certain character, delete (undo) the one just before it". The "one just before" is exactly the top of a stack. So deleting = popping. The teacher finds this the easiest pattern.

2Tiny example: "babbbacc", where two equal neighbours cancel

Rule: if the current character equals the one right before it, both disappear.

Brute force first

For each i, start j = i − 1 and compare. Only the adjacent character matters (a b farther back can't cancel this one). When they match, delete both from the string. Deleting from the middle of a string shifts all later characters left, which is O(n) each time. Over the whole string → O(n²).

With a stack

The stack holds the characters that survive so far. For each new character: if it matches the top, pop (that deletes the earlier one) and don't push the current one (it's deleted too). Otherwise push it. Popping from the top never shifts anything, so each step is O(1).

Read the stack bottom to top: "baba". Check by eye: babbbacc. The circled pairs cancel, and b a b a is left.

3Python template

def remove_pairs(s):
    st = []
    for ch in s:
        if st and st[-1] == ch:              # current cancels the previous survivor
            st.pop()                         # delete the earlier one ...
        else:                                # ... and do NOT push the current one
            st.append(ch)
    return ''.join(st)                       # survivors, bottom to top

Part E · Pattern 4: Parentheses

1The idea

Whenever a question asks you to match brackets, check whether brackets are valid, or count what's needed to make them valid, think stack. An opening bracket alone tells you nothing. The checking only starts when a closing bracket appears, and then you must look back for its partner. Looking back = stack.

The partner of a closing bracket must be the most recent unmatched opening bracket. That's precisely the top of the stack.

2Tiny example: [(()){}]

Stack empty at the end → valid. Without a stack, each closer would start a j loop back towards index 0 to find its partner → O(n²).

3Python template

def is_valid(s):
    partner = {')': '(', ']': '[', '}': '{'}
    st = []
    for ch in s:
        if ch in '([{':
            st.append(ch)                    # opener: just remember it
        else:
            if not st or st[-1] != partner[ch]:
                return False                 # closer with no / wrong opener
            st.pop()                         # matched pair disappears
    return not st                            # leftover openers = invalid

4Space saver: a counter for one bracket type

When there is only one kind of bracket, ( and ), the stack would only ever hold (. So we don't need the items, only how many there are. A plain integer counter does the job in O(1) space. (Not shown in the video. It's the usual follow-up in the parentheses problems of the sheet.)

def min_add_to_make_valid(s):
    open_count = 0                           # '(' still waiting for a ')'
    need_open = 0                            # ')' that had no '(' before them
    for ch in s:
        if ch == '(':
            open_count += 1                  # like a push
        elif open_count > 0:
            open_count -= 1                  # like a pop: matched
        else:
            need_open += 1                   # a ')' with nothing to match
    return need_open + open_count            # brackets we must add

Part F · Pattern 5: Stack-based design

1The idea

Here you're asked to build a data structure using stacks, for example a queue, a min stack or a max stack. The teacher says beginners usually find this pattern tricky, but it isn't really hard, and 3–4 practice problems are enough.

The contrast that matters: a stack is LIFO. Push 1, 2, 3, 4 and pop gives 4 first. A queue is FIFO (First In, First Out). Push 1, 2, 3, 4 and remove gives 1 first, like a line at a ticket counter.

2Tiny example: a queue from two stacks

Use one stack for input (where pushes go) and one for output (where pops come from). When output is empty and someone wants the front, pour all of input into output. Pouring reverses the order, so the oldest item ends up on top of output.

Out came 1, 2, 3, 4, the same order they went in. A queue ✓.

3Why it's still fast: amortised O(1)

A single pop may pour many items, which looks like O(n). But each item is poured at most once in its life: pushed into "in" once, moved to "out" once, popped from "out" once. Over any sequence of k operations the total work is O(k), so the average per operation is O(1). This kind of average-over-a-sequence cost is called amortised.

4Python templates

class MyQueue:
    def __init__(self):
        self.inp = []                        # new items land here
        self.out = []                        # oldest item is on top here

    def push(self, x):
        self.inp.append(x)

    def _move(self):
        if not self.out:                     # pour only when out is empty
            while self.inp:
                self.out.append(self.inp.pop())

    def pop(self):
        self._move()
        return self.out.pop()

    def peek(self):
        self._move()
        return self.out[-1]

    def empty(self):
        return not self.inp and not self.out

class MinStack:
    def __init__(self):
        self.st = []                         # each entry: (value, min of everything up to here)

    def push(self, val):
        cur_min = val if not self.st else min(val, self.st[-1][1])
        self.st.append((val, cur_min))

    def pop(self):
        self.st.pop()

    def top(self):
        return self.st[-1][0]

    def getMin(self):
        return self.st[-1][1]                # O(1): stored alongside the top

Part G · Pattern 6: Recursive stack

1The idea

You get a stack and must change it, for example reverse it, delete the bottom (or the middle) item, or insert an item at the bottom. The catch: no extra data structure is allowed. You may only use the stack itself and recursion.

2Tiny example: delete the bottom of [1, 2, 3, 4]

The obvious way: pop 4, 3, 2 into another list, pop 1 and throw it away, then push 2, 3, 4 back. That uses an extra list, which is not allowed here.

The recursive way: pop the top and hold it in a local variable of the current function call, then call the function again on the smaller stack. When only one item is left, that's the bottom, so remove it. While the calls return, each one pushes its held item back. The "extra storage" is Python's own call stack, not a data structure we built.

3Python templates

def insert_at_bottom(st, x):
    if not st:                               # empty -> x is now the bottom
        st.append(x)
        return
    top = st.pop()                           # hold the top in this call
    insert_at_bottom(st, x)
    st.append(top)                           # put it back on the way out

def reverse_stack(st):
    if not st:
        return
    top = st.pop()
    reverse_stack(st)                        # reverse the rest
    insert_at_bottom(st, top)                # old top goes to the bottom

def delete_bottom(st):
    if not st:
        return
    if len(st) == 1:                         # only the bottom is left
        st.pop()
        return
    top = st.pop()
    delete_bottom(st)
    st.append(top)

Part H · Which sheet problem uses which pattern

Grouped by the technique each problem needs (the sheet's own order may group a few slightly differently):

The teacher's advice: solve at least 3–4 problems from each pattern and tick them off in the sheet as you go.

Part I · Revision page

print(next_greater([2, 4, 3, 8, 1]))     # [4, 8, 8, -1, -1]
print(calculate("2+3*5-4"))              # 13
print(remove_pairs("babbbacc"))          # baba
print(is_valid("[(()){}]"))              # True
print(min_add_to_make_valid("())("))     # 2
q = MyQueue(); q.push(1); q.push(2); q.push(3)
print(q.pop(), q.peek())                 # 1 2
st = [1, 2, 3, 4]; reverse_stack(st)
print(st)                                # [4, 3, 2, 1]

Based on this video: Stack Data Structure | 6 Stack Patterns