Skip to content
C Codeloom
DSA

LeetCode Valid Parentheses: The Classic Stack Problem

A clean walkthrough of LeetCode Valid Parentheses with the optimal stack solution. Covers edge cases, complexity, and how to explain the approach in interviews.

·5 min read · By Yash Kesharwani
Intermediate 9 min read

What you'll learn

  • ✓Why a stack is the natural data structure for matching brackets
  • ✓How to use a small lookup map to keep the code symmetric and short
  • ✓Edge cases like empty strings, leading closers, and unmatched openers
  • ✓A precise complexity analysis you can defend on a whiteboard
  • ✓An interview talk-track that frames the solution in one sentence

Prerequisites

LeetCode 20, Valid Parentheses, is the entry point to the entire stack family of problems. It is officially Easy but interviewers use it as a quick test of vocabulary: do you know which data structure fits the job, and can you implement it cleanly without bugs. This walkthrough covers the stack solution, the few edge cases that trip people up, and the talking points that make your answer sound complete.

The Problem

Given a string s containing just the characters (, ), {, }, [, and ], determine if the input string is valid. A string is valid when every open bracket is closed by the same type of bracket in the correct order.

Examples:

  • () returns true.
  • ()[]{} returns true.
  • (] returns false.
  • ([)] returns false. The brackets interleave instead of nesting.
  • {[]} returns true.

Brute Force

You could repeatedly scan the string and remove adjacent matching pairs until nothing changes, then check whether the result is empty.

def isValid(s: str) -> bool:
    prev = None
    while prev != s:
        prev = s
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

This works but each replace pass is O(n) and we may do O(n) passes, giving O(n^2) time. It also allocates many intermediate strings. We can do better with a single pass.

Optimal Solution

A stack records the open brackets we have seen but not closed. When we hit a closer, the most recent opener must match. If it does not, or if the stack is empty, the string is invalid.

def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

The pairs map turns each closer into the opener it expects, which keeps the loop body symmetric. We push openers, and for closers we check the top of the stack and pop in one step. At the end the stack must be empty, otherwise some openers were never closed.

Walk Through an Example

Take s = "{[()]}".

  • { is an opener, push. Stack is ['{'].
  • [ is an opener, push. Stack is ['{', '['].
  • ( is an opener, push. Stack is ['{', '[', '('].
  • ) is a closer expecting (. The popped value is (, which matches. Stack is ['{', '['].
  • ] is a closer expecting [. The popped value is [, which matches. Stack is ['{'].
  • } is a closer expecting {. The popped value is {, which matches. Stack is [].

We finish with an empty stack, so the answer is true.

Now take s = "([)]".

  • ( is pushed. Stack is ['('].
  • [ is pushed. Stack is ['(', '['].
  • ) expects (. The pop returns [, which does not match, so we return false immediately.

The interleaving is caught on the very first mismatched pop.

Edge Cases

  • Empty string: the loop runs zero times and the stack is empty, so we return true. Some variants treat this as invalid, but LeetCode accepts it.
  • Leading closer: the first character is something like ). The stack is empty when we try to pop, so we return false.
  • All openers: every character is pushed, the stack is non-empty at the end, and we return false.
  • Single character: a single opener or closer is always invalid.
  • Non-bracket characters: the official problem guarantees only bracket characters. If the input could include letters, decide whether to ignore them or reject the input.

Complexity Analysis

Each character is pushed at most once and popped at most once, so total work is linear.

  • Time: O(n).
  • Space: O(n) in the worst case, when every character is an opener and the stack grows to length n.

If O(n) is fuzzy, our note on Big O notation has the basics.

How to Explain It in an Interview

  • State the invariant: the most recently opened bracket must be the first one closed.
  • Name the structure that gives you last-in-first-out access: a stack.
  • Describe the loop: push openers, on a closer compare the top of the stack to the expected opener.
  • Mention the two failure modes explicitly: stack empty when you need to pop, or top of stack does not match.
  • Conclude with the final check that the stack must be empty.

Saying all five points takes thirty seconds and leaves no room for the interviewer to ask whether you forgot a case.

  • LeetCode 22, Generate Parentheses, which uses backtracking with a similar balance idea.
  • LeetCode 32, Longest Valid Parentheses, a harder version with dynamic programming or a stack of indices.
  • LeetCode 921, Minimum Add to Make Parentheses Valid, which counts unmatched brackets in a single pass.

For the underlying structure, revisit stacks and queues. If you want to dig into a related counting trick, hashing and hash maps pairs well with several follow-up problems.

Wrap up

Valid Parentheses is the canonical introduction to stack-based problems. Push when you see an opener, pop and compare when you see a closer, and verify emptiness at the end. The whole loop is six lines, and being able to write and explain it without hesitation is the kind of fluency that gets you to the next round.