Stack Pattern

5 min read—Use LIFO structures for nested parsing and monotonic lookups.

Stack Pattern

A Stack is a fundamental linear data structure that operates on the Last-In, First-Out (LIFO) principle. The last element added to the stack (via "push") is the first one to be removed (via "pop"). This makes stacks highly effective for problems where the most recently visited elements are the most relevant for subsequent decisions—such as managing function calls, backtracking, processing nested structures, or searching for nearby boundaries (monotonic stacks).

By utilizing a stack, we can keep track of historical states and resolve them in reverse order of arrival in O(N)O(N) time.

The Core Concept: Valid Parentheses

To understand this concept deeply, let's explore Valid Parentheses.

Problem Statement: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets and in the correct order.

Naive Brute Force — O(N2)O(N^2)

A naive solution repeatedly searches for matching pairs (like "()", "{}", "[]") and replaces them with an empty string until no more matching pairs are found. If the final string is empty, it is valid:

def isValidBrute(s: str) -> bool: while "()" in s or "{}" in s or "[]" in s: s = s.replace("()", "").replace("{}", "").replace("[]", "") return len(s) == 0

This is highly inefficient because searching and replacing strings takes O(N)O(N) time, and we may have to repeat this up to O(N)O(N) times, resulting in a worst-case time complexity of O(N2)O(N^2).

The Stack Breakthrough — O(N)O(N)

We can solve this in O(N)O(N) time and O(N)O(N) space using a stack.

As we iterate through the string:

  • If we see an opening bracket ('(', '{', '['), we push it onto the stack, saving it to match later.
  • If we see a closing bracket (')', '}', ']'), it must match the most recently opened bracket, which is sitting at the top of the stack.
    • If the stack is empty (meaning there's no matching opener) or the top of the stack does not match the closing bracket, the string is invalid.
    • If it matches, we pop the opener from the stack and continue.
  • After processing the entire string, the stack must be empty (all opened brackets were matched and closed).

This allows us to validate nested structures in a single linear pass.

Step-by-Step Traversal

Let's trace the algorithm on the input string: "({[]})".

Step 1: Initialize Stack

We start by initializing our empty stack.

INITInitialize lookup map of closing to opening brackets: map = { ')': '(', '}': '{', ']': '[' }1 / 24
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
scroll to zoom · drag to pan
124

Step 2: Push Opening Brackets

  • We process character '('. Since it is an opening bracket, we push it onto the stack.
PUSHPush opening bracket '(' onto stack1 / 21
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
Stack
(
◀TOP
scroll to zoom · drag to pan
121
  • Next, we see '{'. It is also an opening bracket, so we push it onto the stack.
PUSHPush opening bracket '{' onto stack1 / 18
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
1
Stack
(
{
◀TOP
scroll to zoom · drag to pan
118
  • Then, we see '['. We push it onto the stack. The stack is now ['(', '{', '['].
PUSHPush opening bracket '[' onto stack1 / 15
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
1
2
Stack
(
{
[
◀TOP
scroll to zoom · drag to pan
115

Step 3: Match and Pop Closing Brackets

  • We see character ']'. Since it is a closing bracket, we check the top of the stack.
  • The top of the stack is '[', which matches ']'.
COMPARETop of stack is '['. Compare with matching opening bracket for ']' ('['): Match!1 / 12
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
1
2
Stack
(
{
[
◀TOP
scroll to zoom · drag to pan
112
  • We pop '[' from the stack. The stack becomes ['(', '{'].
POPPop matching bracket '[' from stack1 / 11
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
1
Stack
(
{
◀TOP
scroll to zoom · drag to pan
111
  • We see character '}'. The top of the stack is '{', which matches '}'.
COMPARETop of stack is '{'. Compare with matching opening bracket for '}' ('{'): Match!1 / 8
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
1
Stack
(
{
◀TOP
scroll to zoom · drag to pan
18
  • We pop '{' from the stack. The stack becomes ['('].
POPPop matching bracket '{' from stack1 / 7
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
Stack
(
◀TOP
scroll to zoom · drag to pan
17
  • We see character ')'. The top of the stack is '(', which matches ')'.
COMPARETop of stack is '('. Compare with matching opening bracket for ')' ('('): Match!1 / 4
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
0
Stack
(
◀TOP
scroll to zoom · drag to pan
14
  • We pop '(' from the stack. The stack is now empty.
POPPop matching bracket '(' from stack1 / 3
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
scroll to zoom · drag to pan
13

Step 4: Done

The string has been fully processed. We verify if the stack is empty.

COMPARELoop finished. Verify if stack is empty: stack.length is 01 / 2
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
scroll to zoom · drag to pan
12

Since the stack is empty, the string has valid parentheses. We return True.

DONEStack is empty! String has valid parentheses. Return true.1 / 1
Input
(
0
{
1
[
2
]
3
}
4
)
5
Active Operation:
a
op
b
=
res
Map
)
(
}
{
]
[
scroll to zoom · drag to pan
11

Code Implementation

def isValid(s: str) -> bool: stack = [] # Map closing brackets to their corresponding opening brackets mapping = {")": "(", "}": "{", "]": "["} for char in s: # If the character is a closing bracket if char in mapping: # Pop the top element from stack if it is not empty, otherwise use dummy top_element = stack.pop() if stack else '#' # If the mapping does not match the popped opening bracket if mapping[char] != top_element: return False else: # It is an opening bracket, push to stack stack.append(char) # Return true if stack is empty (all brackets matched) return len(stack) == 0

Time Complexity: O(N)O(N) — we scan the string once. Each character is pushed and popped at most once. Space Complexity: O(N)O(N) — in the worst case, the stack stores all opening brackets (e.g., "(((((").

Core Variations

1. Nested Parsing / Decoding

Using stacks to decode expressions or strings that are recursively nested.

  • Approach: Push multipliers and characters onto stacks, and when a closing marker is hit, pop and reconstruct the inner segment.
  • Examples: Decode String, Basic Calculator.

2. Monotonic Stack

A stack that maintains its elements in strictly increasing or decreasing order.

  • Approach: When pushing a new element, pop all elements that violate the sorting property. This allows finding the "next greater" or "previous smaller" element in O(N)O(N) overall time.
  • Examples: Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram.

3. Min Stack / Max Stack

A stack that supports retrieving the minimum or maximum element in O(1)O(1) time.

  • Approach: Maintain an auxiliary stack that stores the minimum/maximum element seen so far at each level of the main stack.
  • Example: Min Stack.

When Do I Use This?

Ask yourself these questions:

  1. Does the problem involve processing data where the most recently seen item dictates the next step?
  2. Are you parsing nested structures like parentheses, nested strings, HTML tags, or equations?
  3. Do you need to find the next greater or previous smaller element for each item in a list?

If any of these apply, a Stack is the ideal data structure.

Practice Problems

DoneQuestionDifficulty
Valid ParenthesesEasy
Decode StringMedium
Longest Valid ParenthesesHard
Daily TemperaturesMedium
Largest Rectangle in HistogramHard

How helpful was this content?

Comments

0/2000

Sign in to join the discussion