Data Structures & AlgorithmsStacks

Common Stack Patterns & Problem Types

LevelIntermediate

Duration75 mins

TopicStacks

2 / 4

Tracking State During Traversal

The Memory of Where You've Been

When you walk through a maze, you need to remember where you've been—which turns you've taken, which paths you've explored, how deep you've ventured. Without this memory, you'd wander in circles forever.

Stacks provide exactly this kind of memory for algorithms. As you traverse a sequence or structure, the stack tracks your state: what you've seen, what context you're in, and where you need to return when you backtrack.

This pattern—using a stack to maintain state during traversal—is one of the most versatile in all of computer science. It appears in parsing, expression evaluation, tree traversal, graph algorithms, and anywhere you need to process data with awareness of surrounding context.

What You Will Master

By the end of this page, you will understand how stacks serve as 'algorithmic memory,' recognize the state tracking pattern in various problem types, implement solutions that maintain context during traversal, and connect this pattern to parsing, matching, and hierarchical processing.

The Core Concept: Stack as Contextual Memory

What does 'state tracking' mean?

When we traverse a sequence—whether it's characters in a string, nodes in a tree, or elements in an array—we often need to remember context from earlier in the traversal. This context might include:

What elements we've seen but haven't finished processing
How deeply nested we currently are
Which opening element matches the current closing element
What decisions we made that we might need to reverse

A stack is the perfect data structure for this because:

LIFO matches nesting semantics — The most recently opened context is always the one we need to close first
Automatic depth tracking — Stack size tells us how deep we are
State preservation — Pushed elements retain their data until popped

The Stack as Working Memory

Think of the stack as short-term working memory for your algorithm. As you encounter new contexts, you push them. As you complete contexts, you pop them. At any moment, the top of the stack represents your 'current state' and everything below represents the chain of states you'll return to.

The Traversal Model:

In a typical state-tracking traversal:

for each element in sequence:
    if element opens a new context:
        push context onto stack
    if element closes a context:
        pop from stack and validate/process
    process element with current stack as context

The stack grows when we enter nested contexts and shrinks when we exit them. The current stack state always reflects where we are in the nesting hierarchy.

Classic Example: Parentheses Matching

The canonical example of state tracking is matching parentheses (or brackets, braces, and other paired delimiters). Given a string like "((a + b) * (c - d))", we need to verify that every opening parenthesis has a corresponding closing one, and that they're properly nested.

Why is this a state tracking problem?

When we encounter (, we need to remember it because somewhere later we'll encounter ) that matches it. But we might encounter more ( characters before we see that ). The state we're tracking is: what opening parentheses are still waiting for their match?

The Algorithm:

Traverse the string character by character
When you see (, push it onto the stack (new context opened)
When you see ), pop from the stack (context closed)
If you try to pop from an empty stack, there's an unmatched )
If the stack is non-empty at the end, there are unmatched (s

parentheses-matching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def is_balanced_parentheses(s: str) -> bool:
    """
    Check if parentheses in a string are balanced.
    
    Time Complexity: O(n) - single pass through string
    Space Complexity: O(n) - worst case all characters are '('
    """
    stack = []
    
    for char in s:
        if char == '(':
            # New context opened - push to remember it
            stack.append(char)
        elif char == ')':
            # Context should close - pop to match
            if not stack:
                # No opening parenthesis to match
                return False
            stack.pop()
    
    # Stack should be empty if all parentheses matched
    return len(stack) == 0
 
 
# Test cases
print(is_balanced_parentheses("((a + b))"))       # True
print(is_balanced_parentheses("(a + b) * (c)"))    # True
print(is_balanced_parentheses("((a + b)"))         # False - unmatched (
print(is_balanced_parentheses("(a + b))"))         # False - unmatched )
print(is_balanced_parentheses(")("))               # False - wrong order

Trace Through Example: "((a + b) * c)"

State Tracking During Traversal
Position	Character	Action	Stack State	Context Depth
0	(	Push	[(]	1
1	(	Push	[(, (]	2
2	a	Skip	[(, (]	2
3-5	b	Skip	[(, (]	2
6	)	Pop	[(]	1
7-10	c	Skip	[(]	1
11	)	Pop	[]	0
End	—	Check	[]	0 ✓

State Tracking in Action

The stack size represents our nesting depth at each moment. When we encounter ')', we know exactly which '(' it matches—it's always the one on top of the stack. This is the essence of LIFO matching LIFO nesting.

Extending to Multiple Bracket Types

Real-world applications often involve multiple types of paired delimiters: (), [], {}. The state tracking pattern extends naturally—we push the type of opening bracket and verify that the closing bracket matches.

The Extended Rule:

When we see a closing bracket:

Pop from the stack
Verify the popped opening bracket matches the closing type
If they don't match, the string is invalid

This handles cases like "(]" or "{[}]" correctly—syntactically incorrect even though counts balance.

multiple-brackets.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def is_valid_brackets(s: str) -> bool:
    """
    Check if multiple bracket types are balanced and properly nested.
    
    Handles: (), [], {}
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    # Mapping of closing to opening brackets
    matching = {')': '(', ']': '[', '}': '{'}
    opening = set('([{')
    
    stack = []
    
    for char in s:
        if char in opening:
            # Opening bracket - push to track
            stack.append(char)
        elif char in matching:
            # Closing bracket - must match top of stack
            if not stack:
                return False  # Nothing to match
            
            top = stack.pop()
            if top != matching[char]:
                return False  # Wrong type of bracket
    
    return len(stack) == 0
 
 
# Test cases showing different failure modes
print(is_valid_brackets("()[]{}"))      # True - all matched
print(is_valid_brackets("([{}])"))      # True - nested correctly
print(is_valid_brackets("(]"))          # False - wrong type
print(is_valid_brackets("([)]"))        # False - interleaved wrong
print(is_valid_brackets("{[()]}"))      # True - deeply nested
print(is_valid_brackets("(("))          # False - unclosed

The Interleaving Problem

"([)]" has balanced counts (one of each), but is invalid because brackets are interleaved incorrectly. Stack-based validation catches this because when we see ']', the top of stack is '(' not '['. This is why counting alone is insufficient—we need LIFO state tracking.

Storing Rich Context in the Stack

So far, we've pushed simple characters onto the stack. But the state tracking pattern becomes even more powerful when we store rich context objects containing multiple pieces of information.

Common Context Data:

Position/Index — Where the context started
Value — The element that opened the context
Accumulated data — Partial results computed within the context
Metadata — Any other relevant information

Example: Finding Matching Bracket Positions

Instead of just validating brackets, we want to locate each pair—return the indices of matching brackets.

bracket-positions.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def find_bracket_pairs(s: str) -> list[tuple[int, int]]:
    """
    Find all matching bracket pairs and return their positions.
    
    Returns list of (open_index, close_index) tuples.
    
    Example: "a(b(c)d)e" returns [(3, 5), (1, 7)]
    Note: pairs are returned in order of closing.
    """
    # Stack stores (index, character) tuples - rich context
    stack = []
    pairs = []
    matching = {')': '(', ']': '[', '}': '{'}
    opening = set('([{')
    
    for i, char in enumerate(s):
        if char in opening:
            # Push position AND character
            stack.append((i, char))
        elif char in matching:
            if stack and stack[-1][1] == matching[char]:
                open_pos, _ = stack.pop()
                pairs.append((open_pos, i))
            else:
                # Unmatched closing bracket
                pass  # Could raise error or track separately
    
    return pairs
 
 
# Examples
s = "a(b(c)d)e"
print(f"String: {s}")
print(f"Pairs: {find_bracket_pairs(s)}")
# String: a(b(c)d)e
# Pairs: [(3, 5), (1, 7)]
# (3,5) matches the inner (c)
# (1,7) matches the outer (b...d)
 
s2 = "{arr[i + (j * k)]}"
print(f"String: {s2}")
print(f"Pairs: {find_bracket_pairs(s2)}")
# Pairs: [(9, 15), (4, 16), (0, 17)]

The Power of Position Tracking:

By storing positions, we can:

Report exactly where mismatches occur
Highlight matching pairs in an editor
Navigate between matched delimiters
Build syntax trees where positions matter

This is how IDEs implement bracket highlighting—when you click on a bracket, they use stack-based matching to find its partner instantly.

Nesting Depth Tracking

Another powerful application is tracking nesting depth—how many levels deep we are in nested structures. The stack size itself provides this information for free.

Problem: Maximum Nesting Depth

Given a string of parentheses, find the maximum nesting depth.

"()" → depth 1
"(())" → depth 2
"((()))" → depth 3
"()(())" → depth 2 (two separate nesting regions)

nesting-depth.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def max_nesting_depth(s: str) -> int:
    """
    Find the maximum nesting depth of parentheses.
    
    The stack size at any moment equals current depth.
    Track the maximum size seen.
    
    Time: O(n), Space: O(n) worst case
    """
    stack = []
    max_depth = 0
    
    for char in s:
        if char == '(':
            stack.append(char)
            # Track maximum depth seen
            max_depth = max(max_depth, len(stack))
        elif char == ')':
            if stack:
                stack.pop()
    
    return max_depth
 
 
# Optimized version without actual stack (just counting)
def max_nesting_depth_optimized(s: str) -> int:
    """
    Same result but O(1) space.
    We only need the count, not the actual stack contents.
    """
    current_depth = 0
    max_depth = 0
    
    for char in s:
        if char == '(':
            current_depth += 1
            max_depth = max(max_depth, current_depth)
        elif char == ')':
            current_depth -= 1
    
    return max_depth
 
 
# Test cases
test_cases = [
    "()",           # 1
    "(())",         # 2
    "((()))",       # 3
    "()(())",       # 2
    "(()(()))",     # 3
    "",             # 0
]
 
for tc in test_cases:
    print(f"'{tc}' → depth {max_nesting_depth(tc)}")

When the Stack Itself Is Overkill

For pure depth tracking, we don't need to store actual elements—a counter suffices. But if we need to know WHAT is at each level (not just how deep), the full stack is required. Recognize when you can optimize from O(n) to O(1) space by using counters instead of explicit stacks.

State Tracking in HTML/XML Parsing

HTML and XML are prime examples of nested structures. Tags must be properly opened and closed, with inner tags fully contained within outer tags.

<div>
    <p>Hello <strong>world</strong></p>
</div>

The Stack Approach:

When we see <tag>, push tag onto stack
When we see </tag>, pop and verify it matches
This ensures proper nesting

This is exactly how web browsers and XML parsers work internally.

html-validator.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import re
 
def is_valid_html_nesting(html: str) -> bool:
    """
    Validate that HTML tags are properly nested.
    
    Simplified version - doesn't handle self-closing tags,
    attributes, or comments. Illustrates the core pattern.
    
    Time: O(n) where n is string length
    Space: O(d) where d is maximum nesting depth
    """
    # Regex to find tags (simplified)
    tag_pattern = re.compile(r'<(/?)(w+)>')
    
    stack = []
    
    for match in tag_pattern.finditer(html):
        is_closing = match.group(1) == '/'
        tag_name = match.group(2).lower()
        
        if is_closing:
            # Must match most recently opened tag
            if not stack or stack[-1] != tag_name:
                return False
            stack.pop()
        else:
            # Opening tag - push to track
            stack.append(tag_name)
    
    # All tags must be closed
    return len(stack) == 0
 
 
# Test cases
valid_html = """
<div>
    <p>Hello <strong>world</strong></p>
</div>
"""
 
invalid_html = """
<div>
    <p>Hello <strong>world</p></strong>
</div>
"""
 
print(f"Valid HTML: {is_valid_html_nesting(valid_html)}")    # True
print(f"Invalid HTML: {is_valid_html_nesting(invalid_html)}")  # False

Why LIFO Matches HTML Semantics:

HTML nesting is LIFO by definition:

The most recently opened tag must be closed first
You cannot close an outer tag before closing all inner tags

This isn't just a parsing convenience—it's the fundamental structure of the Document Object Model (DOM). Each tag opens a context that must be closed before the enclosing context can close.

<div>           ← push 'div'
  <p>           ← push 'p'
    <strong>    ← push 'strong'
    </strong>   ← pop, verify 'strong'
  </p>          ← pop, verify 'p'
</div>          ← pop, verify 'div'

Path Tracking in File System Navigation

File system paths involve navigating into directories (going deeper) and navigating out (..). A stack naturally models this navigation.

Problem: Simplify Path

Given a Unix-style file path, simplify it to its canonical form:

/a/./b/../../c/ → /c
. means current directory (no movement)
.. means parent directory (go back up)

This is a classic state tracking problem—the stack tracks which directories we're currently inside.

simplify-path.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def simplify_path(path: str) -> str:
    """
    Simplify a Unix-style file path to its canonical form.
    
    Stack tracks the directory components we're currently in.
    '..' pops (go to parent), '.' does nothing.
    
    Time: O(n) - process each component once
    Space: O(n) - stack stores path components
    """
    # Split by '/' and filter empty strings
    components = path.split('/')
    stack = []
    
    for component in components:
        if component == '' or component == '.':
            # Empty (from //) or current dir - skip
            continue
        elif component == '..':
            # Parent directory - pop if possible
            if stack:
                stack.pop()
            # If stack is empty, we're at root - can't go higher
        else:
            # Valid directory name - push
            stack.append(component)
    
    # Reconstruct canonical path
    return '/' + '/'.join(stack)
 
 
# Test cases
test_paths = [
    "/home/",                    # /home
    "/../",                      # / (can't go above root)
    "/home//foo/",               # /home/foo
    "/a/./b/../../c/",           # /c
    "/a/../../b/../c//.//",      # /c
    "/a/b/c/../../../x/y/z",     # /x/y/z
]
 
for p in test_paths:
    print(f"'{p}' → '{simplify_path(p)}'")

State = Current Location

In this problem, the stack state represents 'where we are right now.' Each directory pushes us deeper; '..' pops us back. The final stack contents directly give the canonical path. This is exactly how file system implementations track the current working directory.

Recognizing State Tracking Problems

Knowing when to apply the state tracking pattern is just as important as knowing how. Here are the signals to watch for:

Recognition Signals

•Matching pairs — Anything that opens must close: brackets, tags, quotes, comments
•Nesting structures — Data with hierarchical depth: HTML, JSON, expressions
•Enter/exit semantics — Concepts like 'enter directory'/'exit directory' or 'start transaction'/'end transaction'
•Most recent first — When closing or backtracking, you deal with the most recently opened item first
•Context-dependent processing — When how you handle an element depends on what's currently 'open'
•Depth tracking — When you need to know how deeply nested you are

State Tracking Problem Types
Problem Domain	What Opens?	What Closes?	Stack Stores
Bracket matching	Opening brackets	Closing brackets	Bracket types
HTML parsing	<tag>	</tag>	Tag names
Expression evaluation	(	)	Partial results
File path navigation	Directory name	..	Path components
Transaction management	BEGIN	COMMIT/ROLLBACK	Transaction IDs
Undo systems	User action	Undo command	Action records

The LIFO Test

Ask yourself: 'Does the most recently opened thing need to be closed first?' If yes, you're looking at a state tracking problem and should reach for a stack.

Summary: State Tracking Mastery

State tracking during traversal is one of the most versatile stack patterns. Let's consolidate the key insights:

Key Takeaways

•Stacks provide algorithmic memory — They remember context from earlier in traversal, available when you need to close or backtrack.
•LIFO matches nesting — Nested structures require closing the innermost context first, exactly what stacks provide.
•Rich context can be stored — Push objects containing position, value, and metadata for more powerful tracking.
•Stack size equals depth — For depth-only problems, a counter may suffice instead of a full stack.
•The pattern is universal — Brackets, HTML, paths, transactions—the same technique applies.
•Recognition is key — Look for open/close pairs, nesting, and most-recent-first semantics.

Pattern Acquired

You now understand how stacks serve as memory during traversal. When you encounter nested structures or matching pairs, the solution pattern is clear: push on open, pop on close, validate or compute during the process.

What's Next:

In the next page, we'll explore function call simulation—how stacks model what happens when functions call other functions. This pattern underlies recursion, call stacks, and is essential for understanding how programs actually execute.

2 / 4

Loading learning content...

Data Structures & AlgorithmsStacks

Common Stack Patterns & Problem Types

LevelIntermediate

Duration75 mins

TopicStacks

2 / 4

Tracking State During Traversal

The Memory of Where You've Been

What You Will Master

The Core Concept: Stack as Contextual Memory

What does 'state tracking' mean?

What elements we've seen but haven't finished processing
How deeply nested we currently are
Which opening element matches the current closing element
What decisions we made that we might need to reverse

A stack is the perfect data structure for this because:

LIFO matches nesting semantics — The most recently opened context is always the one we need to close first
Automatic depth tracking — Stack size tells us how deep we are
State preservation — Pushed elements retain their data until popped

The Stack as Working Memory

The Traversal Model:

In a typical state-tracking traversal:

for each element in sequence:
    if element opens a new context:
        push context onto stack
    if element closes a context:
        pop from stack and validate/process
    process element with current stack as context

The stack grows when we enter nested contexts and shrinks when we exit them. The current stack state always reflects where we are in the nesting hierarchy.

Classic Example: Parentheses Matching

Why is this a state tracking problem?

The Algorithm:

Traverse the string character by character
When you see (, push it onto the stack (new context opened)
When you see ), pop from the stack (context closed)
If you try to pop from an empty stack, there's an unmatched )
If the stack is non-empty at the end, there are unmatched (s

parentheses-matching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def is_balanced_parentheses(s: str) -> bool:
    """
    Check if parentheses in a string are balanced.
    
    Time Complexity: O(n) - single pass through string
    Space Complexity: O(n) - worst case all characters are '('
    """
    stack = []
    
    for char in s:
        if char == '(':
            # New context opened - push to remember it
            stack.append(char)
        elif char == ')':
            # Context should close - pop to match
            if not stack:
                # No opening parenthesis to match
                return False
            stack.pop()
    
    # Stack should be empty if all parentheses matched
    return len(stack) == 0
 
 
# Test cases
print(is_balanced_parentheses("((a + b))"))       # True
print(is_balanced_parentheses("(a + b) * (c)"))    # True
print(is_balanced_parentheses("((a + b)"))         # False - unmatched (
print(is_balanced_parentheses("(a + b))"))         # False - unmatched )
print(is_balanced_parentheses(")("))               # False - wrong order

Trace Through Example: "((a + b) * c)"

State Tracking During Traversal
Position	Character	Action	Stack State	Context Depth
0	(	Push	[(]	1
1	(	Push	[(, (]	2
2	a	Skip	[(, (]	2
3-5	b	Skip	[(, (]	2
6	)	Pop	[(]	1
7-10	c	Skip	[(]	1
11	)	Pop	[]	0
End	—	Check	[]	0 ✓

State Tracking in Action

Extending to Multiple Bracket Types

The Extended Rule:

When we see a closing bracket:

Pop from the stack
Verify the popped opening bracket matches the closing type
If they don't match, the string is invalid

This handles cases like "(]" or "{[}]" correctly—syntactically incorrect even though counts balance.

multiple-brackets.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def is_valid_brackets(s: str) -> bool:
    """
    Check if multiple bracket types are balanced and properly nested.
    
    Handles: (), [], {}
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    # Mapping of closing to opening brackets
    matching = {')': '(', ']': '[', '}': '{'}
    opening = set('([{')
    
    stack = []
    
    for char in s:
        if char in opening:
            # Opening bracket - push to track
            stack.append(char)
        elif char in matching:
            # Closing bracket - must match top of stack
            if not stack:
                return False  # Nothing to match
            
            top = stack.pop()
            if top != matching[char]:
                return False  # Wrong type of bracket
    
    return len(stack) == 0
 
 
# Test cases showing different failure modes
print(is_valid_brackets("()[]{}"))      # True - all matched
print(is_valid_brackets("([{}])"))      # True - nested correctly
print(is_valid_brackets("(]"))          # False - wrong type
print(is_valid_brackets("([)]"))        # False - interleaved wrong
print(is_valid_brackets("{[()]}"))      # True - deeply nested
print(is_valid_brackets("(("))          # False - unclosed

The Interleaving Problem

Storing Rich Context in the Stack

So far, we've pushed simple characters onto the stack. But the state tracking pattern becomes even more powerful when we store rich context objects containing multiple pieces of information.

Common Context Data:

Position/Index — Where the context started
Value — The element that opened the context
Accumulated data — Partial results computed within the context
Metadata — Any other relevant information

Example: Finding Matching Bracket Positions

Instead of just validating brackets, we want to locate each pair—return the indices of matching brackets.

bracket-positions.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def find_bracket_pairs(s: str) -> list[tuple[int, int]]:
    """
    Find all matching bracket pairs and return their positions.
    
    Returns list of (open_index, close_index) tuples.
    
    Example: "a(b(c)d)e" returns [(3, 5), (1, 7)]
    Note: pairs are returned in order of closing.
    """
    # Stack stores (index, character) tuples - rich context
    stack = []
    pairs = []
    matching = {')': '(', ']': '[', '}': '{'}
    opening = set('([{')
    
    for i, char in enumerate(s):
        if char in opening:
            # Push position AND character
            stack.append((i, char))
        elif char in matching:
            if stack and stack[-1][1] == matching[char]:
                open_pos, _ = stack.pop()
                pairs.append((open_pos, i))
            else:
                # Unmatched closing bracket
                pass  # Could raise error or track separately
    
    return pairs
 
 
# Examples
s = "a(b(c)d)e"
print(f"String: {s}")
print(f"Pairs: {find_bracket_pairs(s)}")
# String: a(b(c)d)e
# Pairs: [(3, 5), (1, 7)]
# (3,5) matches the inner (c)
# (1,7) matches the outer (b...d)
 
s2 = "{arr[i + (j * k)]}"
print(f"String: {s2}")
print(f"Pairs: {find_bracket_pairs(s2)}")
# Pairs: [(9, 15), (4, 16), (0, 17)]

The Power of Position Tracking:

By storing positions, we can:

Report exactly where mismatches occur
Highlight matching pairs in an editor
Navigate between matched delimiters
Build syntax trees where positions matter

This is how IDEs implement bracket highlighting—when you click on a bracket, they use stack-based matching to find its partner instantly.

Nesting Depth Tracking

Another powerful application is tracking nesting depth—how many levels deep we are in nested structures. The stack size itself provides this information for free.

Problem: Maximum Nesting Depth

Given a string of parentheses, find the maximum nesting depth.

"()" → depth 1
"(())" → depth 2
"((()))" → depth 3
"()(())" → depth 2 (two separate nesting regions)

nesting-depth.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def max_nesting_depth(s: str) -> int:
    """
    Find the maximum nesting depth of parentheses.
    
    The stack size at any moment equals current depth.
    Track the maximum size seen.
    
    Time: O(n), Space: O(n) worst case
    """
    stack = []
    max_depth = 0
    
    for char in s:
        if char == '(':
            stack.append(char)
            # Track maximum depth seen
            max_depth = max(max_depth, len(stack))
        elif char == ')':
            if stack:
                stack.pop()
    
    return max_depth
 
 
# Optimized version without actual stack (just counting)
def max_nesting_depth_optimized(s: str) -> int:
    """
    Same result but O(1) space.
    We only need the count, not the actual stack contents.
    """
    current_depth = 0
    max_depth = 0
    
    for char in s:
        if char == '(':
            current_depth += 1
            max_depth = max(max_depth, current_depth)
        elif char == ')':
            current_depth -= 1
    
    return max_depth
 
 
# Test cases
test_cases = [
    "()",           # 1
    "(())",         # 2
    "((()))",       # 3
    "()(())",       # 2
    "(()(()))",     # 3
    "",             # 0
]
 
for tc in test_cases:
    print(f"'{tc}' → depth {max_nesting_depth(tc)}")

When the Stack Itself Is Overkill

State Tracking in HTML/XML Parsing

HTML and XML are prime examples of nested structures. Tags must be properly opened and closed, with inner tags fully contained within outer tags.

<div>
    <p>Hello <strong>world</strong></p>
</div>

The Stack Approach:

When we see <tag>, push tag onto stack
When we see </tag>, pop and verify it matches
This ensures proper nesting

This is exactly how web browsers and XML parsers work internally.

html-validator.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import re
 
def is_valid_html_nesting(html: str) -> bool:
    """
    Validate that HTML tags are properly nested.
    
    Simplified version - doesn't handle self-closing tags,
    attributes, or comments. Illustrates the core pattern.
    
    Time: O(n) where n is string length
    Space: O(d) where d is maximum nesting depth
    """
    # Regex to find tags (simplified)
    tag_pattern = re.compile(r'<(/?)(w+)>')
    
    stack = []
    
    for match in tag_pattern.finditer(html):
        is_closing = match.group(1) == '/'
        tag_name = match.group(2).lower()
        
        if is_closing:
            # Must match most recently opened tag
            if not stack or stack[-1] != tag_name:
                return False
            stack.pop()
        else:
            # Opening tag - push to track
            stack.append(tag_name)
    
    # All tags must be closed
    return len(stack) == 0
 
 
# Test cases
valid_html = """
<div>
    <p>Hello <strong>world</strong></p>
</div>
"""
 
invalid_html = """
<div>
    <p>Hello <strong>world</p></strong>
</div>
"""
 
print(f"Valid HTML: {is_valid_html_nesting(valid_html)}")    # True
print(f"Invalid HTML: {is_valid_html_nesting(invalid_html)}")  # False

Why LIFO Matches HTML Semantics:

HTML nesting is LIFO by definition:

The most recently opened tag must be closed first
You cannot close an outer tag before closing all inner tags

This isn't just a parsing convenience—it's the fundamental structure of the Document Object Model (DOM). Each tag opens a context that must be closed before the enclosing context can close.

<div>           ← push 'div'
  <p>           ← push 'p'
    <strong>    ← push 'strong'
    </strong>   ← pop, verify 'strong'
  </p>          ← pop, verify 'p'
</div>          ← pop, verify 'div'

Path Tracking in File System Navigation

File system paths involve navigating into directories (going deeper) and navigating out (..). A stack naturally models this navigation.

Problem: Simplify Path

Given a Unix-style file path, simplify it to its canonical form:

/a/./b/../../c/ → /c
. means current directory (no movement)
.. means parent directory (go back up)

This is a classic state tracking problem—the stack tracks which directories we're currently inside.

simplify-path.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def simplify_path(path: str) -> str:
    """
    Simplify a Unix-style file path to its canonical form.
    
    Stack tracks the directory components we're currently in.
    '..' pops (go to parent), '.' does nothing.
    
    Time: O(n) - process each component once
    Space: O(n) - stack stores path components
    """
    # Split by '/' and filter empty strings
    components = path.split('/')
    stack = []
    
    for component in components:
        if component == '' or component == '.':
            # Empty (from //) or current dir - skip
            continue
        elif component == '..':
            # Parent directory - pop if possible
            if stack:
                stack.pop()
            # If stack is empty, we're at root - can't go higher
        else:
            # Valid directory name - push
            stack.append(component)
    
    # Reconstruct canonical path
    return '/' + '/'.join(stack)
 
 
# Test cases
test_paths = [
    "/home/",                    # /home
    "/../",                      # / (can't go above root)
    "/home//foo/",               # /home/foo
    "/a/./b/../../c/",           # /c
    "/a/../../b/../c//.//",      # /c
    "/a/b/c/../../../x/y/z",     # /x/y/z
]
 
for p in test_paths:
    print(f"'{p}' → '{simplify_path(p)}'")

State = Current Location

Recognizing State Tracking Problems

Knowing when to apply the state tracking pattern is just as important as knowing how. Here are the signals to watch for:

Recognition Signals

•Matching pairs — Anything that opens must close: brackets, tags, quotes, comments
•Nesting structures — Data with hierarchical depth: HTML, JSON, expressions
•Enter/exit semantics — Concepts like 'enter directory'/'exit directory' or 'start transaction'/'end transaction'
•Most recent first — When closing or backtracking, you deal with the most recently opened item first
•Context-dependent processing — When how you handle an element depends on what's currently 'open'
•Depth tracking — When you need to know how deeply nested you are

State Tracking Problem Types
Problem Domain	What Opens?	What Closes?	Stack Stores
Bracket matching	Opening brackets	Closing brackets	Bracket types
HTML parsing	<tag>	</tag>	Tag names
Expression evaluation	(	)	Partial results
File path navigation	Directory name	..	Path components
Transaction management	BEGIN	COMMIT/ROLLBACK	Transaction IDs
Undo systems	User action	Undo command	Action records

The LIFO Test

Ask yourself: 'Does the most recently opened thing need to be closed first?' If yes, you're looking at a state tracking problem and should reach for a stack.

Summary: State Tracking Mastery

State tracking during traversal is one of the most versatile stack patterns. Let's consolidate the key insights:

Key Takeaways

•Stacks provide algorithmic memory — They remember context from earlier in traversal, available when you need to close or backtrack.
•LIFO matches nesting — Nested structures require closing the innermost context first, exactly what stacks provide.
•Rich context can be stored — Push objects containing position, value, and metadata for more powerful tracking.
•Stack size equals depth — For depth-only problems, a counter may suffice instead of a full stack.
•The pattern is universal — Brackets, HTML, paths, transactions—the same technique applies.
•Recognition is key — Look for open/close pairs, nesting, and most-recent-first semantics.

Pattern Acquired

What's Next:

2 / 4