Valid Parentheses: LIFO is exactly what matching brackets need

Before reaching for a data structure, ask what the problem actually requires. Here: you are reading a string left to right, and every time you hit a closing bracket you need to know what the most recently opened bracket was. Not the first one. Not any one. The most recent one.

That is LIFO by definition. A stack is not a trick — it is the direct translation of the constraint into code.

The problem: given a string containing only (, ), {, }, [, ], determine if it is valid. Valid means every opener is closed by the same type, in the correct order, and every closer has a corresponding opener. Two constraints do all the work. 1 <= s.length <= 10^4 rules out O(n²) in practice (though for n = 10,000 a naive quadratic approach still runs, just inefficiently). s consists only of the six bracket characters, so you never need to handle anything else — the mapping is fixed at three pairs.

Brute force: O(n²)

There is a working brute-force approach: repeatedly scan for adjacent matched pairs — (), [], {} — and remove them until nothing changes. If the string is empty at the end, it was valid.

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

public class Solution {
    public bool IsValid(string s) {
        while (s.Contains("()") || s.Contains("[]") || s.Contains("{}")) {
            s = s.Replace("()", "");
            s = s.Replace("[]", "");
            s = s.Replace("{}", "");
        }
        return s.Length == 0;
    }
}

It works on every example in the problem. But consider (((()))): each replace pass strips one inner pair, requiring four passes over a string that starts at length 8. Each string.Replace allocates a new string, so you are burning O(n) memory per pass with up to n/2 passes — O(n²) time, O(n) space across all the intermediate allocations.

More importantly, the approach fights the structure of the problem instead of using it. The problem has nesting. Brute force erases nesting from the outside in. Stack processes it from the inside out — which is what the actual constraint demands.

The stack solution: O(n)

One pass. For every character:

• Opening bracket ((, [, {): push it.
• Closing bracket (), ], }): the stack's top must be the matching opener. If the stack is empty or the top does not match, the string is invalid. Pop and continue.

After the loop, the string is valid only if the stack is empty — meaning every opener was matched and consumed.

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {")": "(", "]": "[", "}": "{"}
        stack = []
 
        for char in s:
            if char in mapping:
                top = stack.pop() if stack else "#"
                if mapping[char] != top:
                    return False
            else:
                stack.append(char)
 
        return not stack

public class Solution {
    public bool IsValid(string s) {
        var mapping = new Dictionary<char, char> {
            { ')', '(' },
            { ']', '[' },
            { '}', '{' }
        };
        var stack = new Stack<char>();
 
        foreach (char c in s) {
            if (mapping.ContainsKey(c)) {
                char top = stack.Count > 0 ? stack.Pop() : '#';
                if (mapping[c] != top) return false;
            } else {
                stack.Push(c);
            }
        }
 
        return stack.Count == 0;
    }
}

O(n) time — one pass, every push and pop is O(1). O(n) space — in the worst case, a string of all openers ((((() fills the stack completely before any closing bracket arrives.

The mapping keys are the closing brackets. When you encounter ), you look up its expected opener ( and compare it against what you pop. Keying on closers is the right choice: you only need the map during a pop decision, not during a push.

By-hand trace through two examples

Example: ([{}]) — should return true.

The state after processing each character:

Step by step in prose form:

char='('  -> opener -> stack=['(']
char='['  -> opener -> stack=['(', '[']
char='{'  -> opener -> stack=['(', '[', '{']
char='}'  -> closer, mapping['}']='{'  top='{' -> match, pop -> stack=['(', '[']
char=']'  -> closer, mapping[']']='['  top='[' -> match, pop -> stack=['(']
char=')'  -> closer, mapping[')']='('  top='(' -> match, pop -> stack=[]
End: stack empty -> return True

The innermost pair closes first. That is the whole point. The stack's LIFO behavior naturally enforces the nesting requirement without any special logic.

Example: ([)] — should return false.

char='('  -> opener -> stack=['(']
char='['  -> opener -> stack=['(', '[']
char=')'  -> closer, mapping[')']='('  top='[' -> mismatch -> return False

The problem is caught immediately at the third character. You opened [ most recently, but then tried to close ( before closing [. Stack detects this because the top is [, not (.

Edge cases, each one accounted for

Empty stack on a closing bracket. You hit ) and the stack has nothing in it. No opener to match. The Python solution handles this with stack.pop() if stack else "#" — the sentinel "#" will never equal any bracket character, so mapping[char] != top fires and you return False. In C#, stack.Count > 0 ? stack.Pop() : '#' does the same thing. Do not call pop() unconditionally; you will get an InvalidOperationException in C# or an IndexError in Python.

Non-empty stack at the end. ((( pushes three times and never pops. The loop exits cleanly, but return not stack is False because three unmatched openers remain. A common mistake is returning True unconditionally here — it passes most examples but fails any string of only openers.

String of all closers. ))) hits an empty stack on the very first character and returns False immediately. No special handling needed; the empty-stack sentinel covers it.

Wrong nesting order. ([)] — covered by the trace above. The stack's top is always the most recently opened bracket, so a cross-close like this is caught at the moment the wrong closer arrives.

Odd length. Any string of odd length cannot be valid — you cannot pair an odd number of brackets. Checking if len(s) % 2 == 1: return False upfront halves the input before the loop. The current code handles odd-length strings correctly without this check (the stack will be non-empty at the end), but adding it is a clean early-exit optimization worth mentioning if you are in an interview.

Single character. ( pushes once and exits with a stack of size 1 — not stack is False. ) hits the empty-stack sentinel and returns False immediately.

Why the stack is the natural fit, not just a valid fit

Consider ([{}]). The innermost pair {} closes first. Then []. Then (). Each bracket type closes in the reverse of the order it opened. That reverse-of-opening-order is the literal definition of a stack's pop sequence.

Contrast this with a queue, which would give you first-in-first-out. A queue would pop ( when you try to match {. That is wrong by construction. The data structure and the problem constraint are aligned at the level of the concept, not just at the level of the implementation. That alignment is what you want to recognize and explain in an interview.

I'd ship the stack solution without hesitation. The brute-force approach is fine as a proof of concept, but the repeated string allocation and O(n²) behavior make it unsuitable for any real-world input. The stack version runs in linear time, uses a constant-size mapping, and the code is short enough to write from memory.

Complexity comparison

Both use O(n) space but for different reasons. Brute force allocates new strings repeatedly. The stack solution uses O(n) stack space — unavoidable, because you may need to hold all openers before seeing any closer.

Pattern recognition

Reach for a stack when:

• The problem involves matching or pairing elements (brackets, tags, quotes, function calls).
• The order of pairing matters: the most recently opened must be the first closed.
• Keywords in the problem: "valid", "balanced", "matching", "nested", "parentheses".

This is the bracket-matching pattern. Once you recognize it, the stack solution follows mechanically: push openers, pop and verify on closers, check empty at the end.

Related problems

LeetCode 22 — Generate Parentheses: generate all combinations of n pairs of valid parentheses. Backtracking with open/close counts — the validity insight from this problem carries over directly.

LeetCode 32 — Longest Valid Parentheses: find the length of the longest valid parentheses substring. Harder. Stack of indices rather than characters; the twist is tracking start positions.

LeetCode 301 — Remove Invalid Parentheses: remove the minimum number of brackets to make the string valid. BFS or backtracking — you need to explore which brackets to remove.

LeetCode 921 — Minimum Add to Make Parentheses Valid: count how many brackets need to be inserted. Track open and close imbalances in one pass — no stack needed, just two counters.

LeetCode 1021 — Remove Outermost Parentheses: strip the outermost layer from each valid group. Depth counter variant of this same bracket-reading loop.

What comes next in this series

This problem introduces the stack pattern. The problems that follow show it scaling to harder constraints:

Min Stack (155) — the stack must also answer getMin() in O(1). You maintain a second stack tracking the minimum at each level, updated on every push.

Daily Temperatures (739) — find how many days until a warmer temperature. A monotonic stack of indices, where you pop when the current temperature exceeds the temperature at the stored index.

Evaluate Reverse Polish Notation (150) — process a postfix expression. Operands go on the stack; each operator pops two operands, applies the operation, pushes the result. The same push-on-open, pop-on-close shape — just with numbers and operators instead of brackets.

Each problem adds a constraint that the brute force cannot absorb cleanly. The stack absorbs all of them.