Day 9: The Only 5 Stack Patterns You Need for DSA Interviews

Matching, Monotonic, Expression, Augmented, Simulation

In DSA, Stack is an unavoidable data structure because from Operating System to JavaScript, everything runs on stack concepts.

Stack is very simple.
You insert a value, and you take out a value. That’s it.

But there is one strict rule → when you take a value, only the last inserted value will come out.

This is called First In Last Out (FILO).

Even though the operations are simple, stack problems are not random.
Almost all stack problems follow some fixed patterns.

There are 5 important stack patterns:

• Matching

• Monotonic

• Expression

• Augmented

• Simulation

We will see them one by one.

---

1. Matching

The matching pattern is used when one element depends on another element and they must form a valid pair.

For example, take LeetCode problem Valid Parentheses:
https://leetcode.com/problems/valid-parentheses/

The problem is simple:
you want to check whether the given parentheses string is valid or not.

The string can contain:

• ( )

• { }

• [ ]

A parentheses string is valid only if:

• every opening bracket has a matching closing bracket

• brackets are closed in the correct order

We use stack.

• If we see an opening bracket, push it into the stack

• If we see a closing bracket:

  • stack should not be empty

  • top of stack must be the same type

  • then pop it

If at any point:

• stack is empty and we get a closing bracket → invalid

• closing bracket doesn’t match the top → invalid

After processing the entire string:

• if stack is empty → valid

• else → invalid

---

2. Monotonic Stack

The Monotonic Stack pattern is used when you need to compare elements with previous or next elements and maintain a specific order inside the stack.

“Monotonic” simply means:

• values in stack are always increasing
  or

• values in stack are always decreasing

No randomness allowed.

Simple Rule (Memorize This) [Increasing Monotonic Stack]

1. Go from left to right

2. Keep numbers in stack

3. If current number is Smaller than stack top:

   • pop Bigger ones until the stack becomes current number > stack top

   • assign answer to them

4. Push current number

Repeat.

Let’s take LeetCode 1475 – Final Prices With a Special Discount in a Shop
https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/

Here, we want to find the next smallest (or equal) value for every price.

Because we are searching for the next smaller element on the right,
we need a Monotonic Increasing Stack

General Monotonic Stack Rule (This Is the Pattern)

Next Smaller Element → Increasing stack

Next Greater Element → Decreasing stack

Find Next one → Left to Right

Find Previous one → Right to Left

Common Problems Using This Pattern

• Next Greater Element

• Next Smaller Element

• Stock Span

• Largest Rectangle in Histogram

• Daily Temperatures

---

3. Expression Stack Pattern

The Expression pattern is used when you are dealing with mathematical or logical expressions where:

• order of execution matters

• operators depend on operands

• brackets change priority

There are three main formats

1. Infix

3 + (5 * 2)

Pattern:

This is where two stacks are used:

• one stack for operands

• one stack for operators

Rules:

• If number → push to operand stack

• If ( → push to operator stack

• If ) → solve until ( is found

• If operator:

  • while top operator has higher or equal precedence

    • solve it

  • then push current operator

At the end:

• solve remaining operators

2. Postfix

3 5 2 * +

Pattern:

• Scan from left to right

• If operand → push to stack

• If operator:

  • pop two values

  • apply operator

  • push result back

At the end:

• stack will have one value

• that is the answer

3. Prefix

+ 3 * 5 2

Pattern:

• Scan from right to left

• If operand → push

• If operator:

  • pop two values

  • apply operator

  • push result

Same logic, just reversed traversal.

Infix Expression pseudocode

---

4. Augmented Stack Pattern

A normal stack where each element carries extra information to avoid recomputation.

For example, let’s take LeetCode 901:
https://leetcode.com/problems/online-stock-span/

The problem is simple:

You are getting stock prices day by day.

For every new price, you want to find the span.

Span means:

How many consecutive days (including today)
the stock price was less than or equal to today’s price.

Input
[”StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”]
[[], [100], [80], [60], [70], [60], [75], [85]]

Output
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today’s price of 75) were less than or equal to today’s price.
stockSpanner.next(85);  // return 6

Here the solution needs O(1) time complexity per operation.

So you cannot traverse the array every time
because that will become O(n) per call.

Instead, you must reuse previous results for the next element.

This is exactly where Augmented Stack works.

This problem needs:

• Monotonic Stack → to maintain order of prices

• Augmented Stack → to store span so we don’t recompute

---

5 . Simulation Stack Pattern

Simulation is nothing but instead of thinking in pattern think in real world problem how you solve

for example we will take LeetCode 735

https://leetcode.com/problems/asteroid-collision/

The problem is, an array is given like

a = [5, 10, -5]

Here we consider each number as an asteroid.

• positive number → asteroid moving right

• negative number → asteroid moving left

• value → size of asteroid

The output will be:

[5, 10]

Explanation:

• 10 and -5 collide, 10 survives

• 5 and 10 never collide because both move right

Instead of thinking pattern wise,
if we think problem wise (real world), we can solve it.

Simulation

1. Asteroids move at the same speed

2. A collision happens only when:

   • one asteroid is moving right

   • and the next asteroid is moving left

3. When they collide:

   • bigger one survives

   • smaller one is destroyed

   • if same size → both destroyed

4. A surviving asteroid can collide again with earlier ones

Nothing else happens.

Pseudocode

---

These are three important patterns you want to practice in stack.

Not because interviewers like patterns,
but because almost every stack problem falls into one of these.

Thank You

---