Parentheses / Matching

Valid Parentheses

Push every opening bracket onto the stack. When you see a closing bracket, check if the stack's top has the matching opener. If yes, pop it. If no (or stack is empty), it's invalid. Stack must be empty at the end.

O(n)

How It Works

Bracket validation is a nesting problem, and stacks model nesting exactly: the most recently opened bracket must be the first one closed, which is LIFO order. Scan the string once. Push every opening bracket; on a closing bracket, the stack top must be its matching opener — pop it if so, otherwise the string is invalid. Seeing a closer with an empty stack, or finishing with leftover openers, also fails.

This runs in O(n) time with O(n) worst-case space for a string of all openers. No comparison-counting or regex trick matches this simplicity, because bracket languages are not regular — counting alone cannot verify that types interleave correctly, as in the invalid string "([)]".

Step-by-Step Visualization

Read '(' → it's an opener, push to stack

Input

(

{

[

]

}

)

Stack

(

ActionPUSH (

1/7

Code

Java

static boolean isValid(String s) {
  Stack<Character> stack = new Stack<>();
  Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

  for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
      stack.push(c); // Push openers
    } else {
      // Closing bracket: check if it matches stack top
      if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
        return false;
      }
    }
  }

  return stack.isEmpty(); // All matched?
}

// Example: isValid("({[]})")
// Answer: true

Tips & Gotchas

1Only push opening brackets onto the stack

2When you see a closing bracket, the stack top MUST be its matching opener

3At the end, the stack must be empty (all brackets matched)

4Can be extended to handle other paired symbols

Practice Problems

1Valid Parentheses
2Longest Valid Parentheses
3Check if a Parentheses String Can Be Valid
4Valid Parenthesis String

About the Parentheses / Matching Pattern

Stacks naturally handle nested structures. Push opening symbols, pop when you find their closing match. If the stack is empty at the end and every match was correct, the expression is valid.

Key insight

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Common Stack Interview Problems

Valid Parentheses
Next Greater Element
Largest Rectangle in Histogram
Trapping Rain Water
Daily Temperatures
Decode String

Frequently Asked Questions

Can I just count openers and closers instead of using a stack?

Only when there is a single bracket type. A counter that increments on '(' and decrements on ')' works for pure parentheses, but with mixed types like '([)]' the counts balance while the nesting is wrong, so you need the stack to remember which type is open.

What are the classic edge cases to test?

An empty string (valid), a string starting with a closer (immediate failure on empty stack), leftover openers at the end like '(((', and interleaved types such as '([)]'. Covering these four catches nearly every implementation bug.