Valid Parentheses — The Classic Stack Pattern

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

•Comfort with stacks and queues
•Basic string iteration

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.

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.

Intuition

You could repeatedly scan the string and remove adjacent matching pairs like (), [], {} until nothing changes, then check whether the result is empty. That works but is O(n^2) time and allocates many intermediate strings.

The right tool is a stack. 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. A small map turning each closer into the opener it expects keeps the loop body short and symmetric. At the end the stack must be empty, otherwise some openers were never closed.

The invariant is simple: the most recently opened bracket must be the first one closed. That is the textbook definition of LIFO, which is exactly what a stack provides.

Explanation with 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.

char   action       stack (top on right)
{    push          [ {                  ]
[    push          [ {  [               ]
(    push          [ {  [  (            ]
)    pop ( ok      [ {  [               ]
]    pop [ ok      [ {                  ]
}    pop { ok      [                    ]

end: stack empty  ->  return True

Stack state across s = {[()]}

char   action       stack
(    push          [ (        ]
[    push          [ (  [     ]
)    pop expects ( top is [  MISMATCH
                                return False

Mismatch trips the check on s = ([)]

Code

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

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char ch : s.toCharArray()) {
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(ch)) return false;
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char,char> pairs = {{')','('},{']','['},{'}','{'}};
        for (char ch : s) {
            if (pairs.count(ch)) {
                if (st.empty() || st.top() != pairs[ch]) return false;
                st.pop();
            } else {
                st.push(ch);
            }
        }
        return st.empty();
    }
};

Edge Cases

Empty string: the loop runs zero times and the stack is empty, so we return true.
Leading closer: the first character is a closer 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: not present in the standard problem; clarify with the interviewer if input could include letters.

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 LIFO 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.

Generate Parentheses, which uses backtracking with a similar balance idea.
Longest Valid Parentheses, a harder version with DP or a stack of indices.
Minimum Add to Make Parentheses Valid, which counts unmatched brackets in a single pass.

For the underlying structure, revisit stacks and queues.

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.