Interview frequency: ⭐⭐⭐⭐⭐
We are continuing from Arrays → Hash Maps → Two Pointers → Sliding Window → Binary Search.
Today you'll learn Stacks from a real coding interview perspective, including the important Monotonic Stack pattern used in medium and hard problems.
1. What is a Stack?
A stack follows LIFO:
Last In, First Out.
Think of a stack of plates. The last plate you put on is the first one you remove.
Stack visualization
LIFO
30 — Top
20
10 — Bottom
Push and pop happen at the top.
Python implementation
Python lists work as stacks.
Python
Run
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
# Pop
print(stack.pop()) # 30
print(stack) # [10, 20]
Time complexity
Python list
Push (append)
O(1) amortized
Pop (pop())
O(1)
Peek (stack[-1])
O(1)
Check empty
O(1)
Interview tip: Never use pop(0) for a stack. It takes O(n). For a queue, use collections.deque.
2. When should you think "Stack"?
These are the major clues:
Matching parentheses or brackets.
Undo / redo operations.
Nested structures.
Next greater or smaller element.
Previous greater or smaller element.
Removing elements based on previous elements.
Evaluating expressions.
The most important recognition rule:
If the problem asks about the nearest previous or next element that satisfies a condition, think Monotonic Stack.
3. Interview Problem #1: Valid Parentheses
LeetCode 20 — Easy, but very important.
Problem
Given a string containing (), {}, and [], determine whether the brackets are valid.
Examples:
"()[]{}" → True
"([{}])" → True
"(]" → False
"([)]" → False
Interviewer's expectation
You should recognise that brackets need to close in the reverse order they open.
That is exactly LIFO → Stack.
Step-by-step thinking
For:
"({[]})"
Stack
(
(
{
( {
[
( { [
]
( {
}
(
)
Empty
Every closing bracket must match the latest opening bracket.
Python solution
Python
Run
def is_valid(s):
stack = []
pairs = {
')': '(',
']': '[',
'}': '{'
}
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return len(stack) == 0
Complexity
Time: O(n)
Space: O(n)
Common mistakes
Popping from an empty stack.
Checking only whether a bracket exists, rather than matching the correct type.
Forgetting to check that the stack is empty at the end.
4. Interview Problem #2: Min Stack
LeetCode 155 — Medium
Problem
Design a stack that supports:
push(x)
pop()
top()
getMin()
All operations must be O(1).
Example:
Python
Run
push(5)
push(3)
push(7)
push(2)
Minimum:
2
After popping 2, minimum becomes:
3
Why a normal stack is not enough
If you scan the whole stack every time you want the minimum:
Python
Run
min(stack)
That takes O(n).
The interviewer wants O(1).
Key idea: Two stacks
stack: stores all values.min_stack: stores the minimum value at each stage.
Python
Run
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack:
self.min_stack.append(val)
else:
self.min_stack.append(
min(val, self.min_stack[-1])
)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
Complexity
Time
Push
O(1)
Pop
O(1)
Top
O(1)
Get minimum
O(1)
This is a great example of using extra memory to optimise time.
5. Monotonic Stack ⭐⭐⭐⭐⭐
This is the advanced part of today's topic.
A monotonic stack maintains elements in either:
Increasing order.
Decreasing order.
It is used when you need to find the next or previous greater/smaller element efficiently.
Example: Next Greater Element
Given:
Python
Run
nums = [2, 1, 5, 3, 4]
For every element, find the first greater element to its right.
Expected output:
Python
Run
[5, 5, -1, 4, -1]
Explanation:
Next greater
2
5
1
5
5
-1
3
4
4
-1
Brute force
For each element, scan everything to the right.
Python
Run
def next_greater_brute(nums):
result = []
for i in range(len(nums)):
found = -1
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
found = nums[j]
break
result.append(found)
return result
Complexity:
Time: O(n²)
Space: O(n)
Optimised: Monotonic decreasing stack
We process the array from right to left.
Why?
Because the answer for an element is somewhere on its right.
Python
Run
def next_greater(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(nums[i])
return result
Dry run
For:
Python
Run
[2, 1, 5, 3, 4]
Start from the right:
Stack after processing
Answer
4
[4]
-1
3
[4, 3]
4
5
[5]
-1
1
[5, 1]
5
2
[5, 2]
5
Final:
Python
Run
[5, 5, -1, 4, -1]
Why is it O(n)?
Every element:
Enters the stack once.
Leaves the stack at most once.
Therefore, total stack operations are O(n).
Time: O(n)
This is called amortized analysis.
6. Important Monotonic Stack Problems
Pattern
Next Greater Element
Decreasing stack
Daily Temperatures
Decreasing stack of indices
Next Greater Element II
Circular array
Stock Span
Previous greater element
Largest Rectangle in Histogram
Previous/next smaller
Sum of Subarray Minimums
Contribution counting
Trapping Rain Water
Stack-based solution
Daily Temperatures — Very Important
LeetCode 739 — Medium
Problem
Given daily temperatures, return how many days you must wait until a warmer temperature.
Python
Run
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output:
Python
Run
[1, 1, 4, 2, 1, 1, 0, 0]
Why use a stack?
For each day, find the next greater temperature to the right.
The stack stores indices of temperatures that are waiting for a warmer day.
Python solution
Python
Run
def daily_temperatures(temperatures):
result = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temp > temperatures[stack[-1]]:
prev = stack.pop()
result[prev] = i - prev
stack.append(i)
return result
Complexity
Time: O(n)
Space: O(n)
Interview insight: Store indices, not just values, because the answer asks for the number of days.
7. Stack vs Queue vs Heap
Main behavior
Python
Stack
LIFO
list
Queue
FIFO
deque
Heap
Priority-based removal
heapq
We will cover queues and heaps in their own topics.
8. Interview Cheat Sheet
Matching brackets
Use a normal stack.
Next greater / smaller
Think monotonic stack.
Need O(1) minimum or maximum
Consider an auxiliary stack.
Practice: Your interview question
Try this before looking at the solution.
Question: Remove adjacent duplicates
Given a string, remove adjacent duplicate characters repeatedly.
Examples:
"abbaca" → "ca"
"azxxzy" → "ay"
For "abbaca":
a b b a c a
↑ ↑
Remove "bb"
a a c a
↑ ↑
Remove "aa"
c a
Your task
Write a Python function:
Python
Run
def remove_duplicates(s):
pass
Return the final string after all adjacent duplicates are removed.
Hint: Use a stack. If the current character equals the top of the stack, pop it. Otherwise, push it.
Next topic
Topic 7: Queues, Deques & BFS basics
We'll learn FIFO, Python's collections.deque, and how queues are used in real interview problems such as Number of Islands and Binary Tree Level Order Traversal.
Top comments (0)