Valid Parentheses

Why it belongs on this sheet

This is a fast stack problem that should feel automatic before you move into trickier stateful questions.

Pattern

Expected closing bracket stack

Approach

Push the expected closing bracket for every opening bracket. For a closing bracket, the top of the stack must match it.

Java solution

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
  public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char ch : s.toCharArray()) {
      if (ch == '(') {
        stack.push(')');
      } else if (ch == '{') {
        stack.push('}');
      } else if (ch == '[') {
        stack.push(']');
      } else if (stack.isEmpty() || stack.pop() != ch) {
        return false;
      }
    }

    return stack.isEmpty();
  }
}

Complexity

• Time: O(n)
• Space: O(n)

Interview note

Pushing expected closers usually reads cleaner than storing openers and matching later.