LeetCode #20 — Easy

Valid Parentheses

A complete visual walkthrough of the stack-based approach — from brute force to the elegant one-pass solution.

Patterns Used
📚Monotonic Stack→

Roadmap

  1. The Brute Force — Repeated Removal
  2. The Core Insight — Use a Stack
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Demo
  7. Complexity Analysis
Step 01

The Brute Force — Repeated Removal

The naive approach: repeatedly scan the string and remove any adjacent matching pairs (), {}, or []. Keep going until nothing changes. If the string becomes empty, it was valid.

Example: "{[()]}"

start
{
[
(
)
]
}
↓ remove ()
pass 1
{
[
]
}
↓ remove []
pass 2
{
}
↓ remove {}
pass 3 empty string = valid

This works, but each pass scans the entire string and we may need up to n/2 passes. That gives us O(n²) time in the worst case — far too slow for large inputs.

💡

The problem with brute force: We're re-scanning the same characters over and over. What if we could process each character exactly once and remember what we've seen? That's where a stack comes in.

Step 02

The Core Insight — Use a Stack

A stack is the perfect data structure for matching nested pairs. The rule is simple:

The Stack Strategy

Opening bracket: ( [ {
Push the expected closing bracket onto the stack.
Closing bracket: ) ] }
Pop from the stack and check if it matches the current character.
Mismatch or empty stack
Return false immediately — the string is invalid.
After processing all characters
Stack must be empty. If not, there are unmatched opening brackets.

Here is the visual idea. Watch how the stack grows when we encounter opening brackets and shrinks when we find matching closing brackets:

Stack Growing and Shrinking

read {
}
read [
}
]
read ] pop ]
}
read } pop }
empty
⚡

Clever trick: Instead of pushing the opening bracket and then mapping to its pair later, we push the expected closing bracket. That way, when we see a closing bracket, we just check stack.pop() == c — no mapping table needed!

Step 03

Algorithm Walkthrough

Let's trace through the input {[]} step by step, watching the stack at each stage.

Processing "{[]}" Character by Character

Read { → opening bracket
Push expected closing }
{
stack:
}
Read [ → opening bracket
Push expected closing ]
[
stack:
}
]
Read ] → closing bracket
Pop ] — matches! ✓
]
stack:
}
Read } → closing bracket
Pop } — matches! ✓
}
stack: empty
Stack empty after all characters → VALID ✓

Now let's see what happens with an invalid input: ([)]

Processing "([)]" — Invalid Case

Read ( → push )
(
stack:
)
Read [ → push ]
[
stack:
)
]
Read ) → pop ]
Expected ] but got ) — MISMATCH ✗
)
STOP
Mismatch detected → INVALID ✗
Step 04

Edge Cases

Before coding, let's identify all the tricky inputs and how the stack handles them:

""
✓ valid
Empty string has no unmatched brackets. Stack starts empty, stays empty.
"((("
✗ invalid
Only opening brackets. Stack has 3 items at end — not empty, so invalid.
")"
✗ invalid
Only closing. Stack is empty when we try to pop — immediate failure.
"({)"
✗ invalid
Odd length is always invalid — you can never match all brackets with odd count.
"((()))"
✓ valid
Deeply nested — stack grows to 3, then shrinks back to 0. Works perfectly.
"([)]"
✗ invalid
Interleaved wrong. Brackets overlap instead of nesting. Pop mismatch detected.
🎯

Quick optimization: If the string length is odd, return false immediately — you can never pair up an odd number of brackets. This avoids unnecessary work.

Step 05

Full Annotated Code

class Solution {
    public boolean isValid(String s) {

        // Use ArrayDeque as a stack (faster than Stack class)
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {

            // Opening bracket? Push the EXPECTED closing bracket
            if (c == '(')      stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');

            // Closing bracket? Pop and check for match
            // If stack is empty or top doesn't match → invalid
            else if (stack.isEmpty() || stack.pop() != c)
                return false;
        }

        // Valid only if all opening brackets were matched
        return stack.isEmpty();
    }
}
📝

Why push the closing bracket? By pushing the expected closing bracket instead of the opening one, the matching logic becomes a simple equality check: stack.pop() != c. No need for a separate Map or switch statement to look up pairs.

Step 06

Interactive Demo

Enter any bracket string and step through the algorithm one character at a time. Watch the stack grow and shrink in real time.

⚙ Stack Visualizer


empty
Step 07

Complexity Analysis

Time
O(n)
Space
O(n)

We process each character exactly once in a single pass through the string, giving O(n) time. In the worst case (all opening brackets like "((((("), the stack holds all n characters, so space is O(n).

Comparison with Brute Force

BRUTE FORCE
O(n²)
Repeated scanning and string manipulation
STACK
O(n)
Single pass, each character touched once
📝

Can we do better on space? Not in general. We need to remember the nesting order of opening brackets. The stack is the minimal data structure for this. However, the early-exit on odd length and on first mismatch means we often use far less than O(n) in practice.