Valid Parentheses

The problem

Given a string containing only parentheses, curly brackets, and square brackets, determine if the input string is valid. Brackets must close in the correct order, match their corresponding open bracket types, and every closing bracket must have an open counterpart.

Every closing bracket can only match the most recently opened, unmatched opening bracket. Inner scopes must resolve completely before outer scopes can close. Because the most recent bracket entered is the earliest bracket required to leave, the structure mirrors a last-in first-out sequence where opening brackets wait on a stack.

Full solution

LIFO bracket stack: push open brackets, and on a closing bracket check the stack top matches before popping — the only approach that stays O(n) instead of the quadratic substring-erasure alternative.

def is_valid(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

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

The theory behind it

Stack — the ground this problem stands on. All Stack problems

What Stack is

A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.

When to reach for it

Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.

How the pattern works

Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.

What each operation costs

Which roles need this problem

Stack is a core topic for these 8 roles — if you're targeting one of them, this problem is early in your path, not optional.

Secondary for 9 more roles, including Frontend Engineer, Data Engineer, Game Developer.