Valid Parentheses: Optimal Solution (Data-Backed Guide)

The Data: Why 48 Companies Ask This

Valid Parentheses is asked universally because it is the simplest possible problem that requires a stack. If you solve it with any other approach, you either make it too complex or miss edge cases. Interviewers use it to verify that you understand when and why to use a stack — a skill that transfers directly to harder problems like Largest Rectangle in Histogram, Daily Temperatures, and Decode String.

Problem Statement

LeetCode #20 — Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Input:  s = "()"        Output: true
Input:  s = "()[]{}"   Output: true
Input:  s = "(]"       Output: false
Input:  s = "([)]"     Output: false  // wrong order
Input:  s = "{[]}"     Output: true   // correctly nested
Input:  s = "("        Output: false  // unclosed bracket
Input:  s = "]"        Output: false  // no matching open

The Core Intuition: Why a Stack?

The key property of valid bracket sequences: the most recently opened bracket must be the first one closed. This is exactly the Last-In-First-Out (LIFO) property of a stack.

Think of it like nested boxes. When you open a box (push to stack), the next thing you close must be that same box (pop from stack and verify match). You can't close an outer box before closing the inner ones.

The Algorithm: Stack-Based Matching

1. Create an empty stack and a hash map: closing → opening (e.g., ')' → '(').
2. Iterate through each character in s:
   • If it's an opening bracket ((, [, {) → push to stack.
   • If it's a closing bracket:
     • If stack is empty → return false (nothing to match).
     • Pop the top. If it doesn't match the expected opener → return false.
3. Return true if stack is empty, false otherwise.

Visual Walkthrough

Tracing s = "{[]}":

Tracing s = "([)]" — the tricky case:

Code in Python, Java & JavaScript

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            # Closing bracket
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            # Opening bracket
            stack.append(char)

    return not stack  # True if all brackets matched

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');

        for (char c : s.toCharArray()) {
            if (mapping.containsKey(c)) {
                // Closing bracket
                char top = stack.isEmpty() ? '#' : stack.pop();
                if (mapping.get(c) != top) return false;
            } else {
                // Opening bracket
                stack.push(c);
            }
        }

        return stack.isEmpty();
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const mapping = { ')': '(', '}': '{', ']': '[' };

    for (const char of s) {
        if (mapping[char]) {
            // Closing bracket
            const top = stack.length ? stack.pop() : '#';
            if (mapping[char] !== top) return false;
        } else {
            // Opening bracket
            stack.push(char);
        }
    }

    return stack.length === 0;
};

Complexity Analysis

Interview-ready explanation: "Time is O(n) — one pass, constant work per character. Space is O(n) in the worst case when the entire string is opening brackets and nothing has been matched yet."

Edge Cases That Trip People Up

Stack Problem Family: 6 Must-Know Variants

Valid Parentheses is the entry point to a family of stack problems. Every variant uses the same core push/pop mechanic — just with more complex conditions.

Variant 1: Minimum Remove to Make Valid Parentheses (LC #1249)

"Remove the minimum number of brackets to make the string valid."

Insight: Use a stack to track indices of unmatched opening brackets. After scanning, all indices still in the stack (unmatched opens) plus positions of unmatched closes must be removed.

Variant 2: Longest Valid Parentheses (LC #32)

"Find the length of the longest valid parentheses substring."

Insight: Push indices onto the stack instead of characters. When a match is found, the current valid length is right_index - stack_top_index. Push -1 as a sentinel base.

def longestValidParentheses(s):
    stack = [-1]  # sentinel base index
    max_len = 0

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # new base
            else:
                max_len = max(max_len, i - stack[-1])

    return max_len

Variant 3: Daily Temperatures (LC #739)

"For each day, find how many days until a warmer temperature."

Insight: Monotonic stack — push indices of unresolved days. When a warmer day arrives, pop and calculate the difference.

def dailyTemperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []  # indices waiting for a warmer day

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

Variant 4: Decode String (LC #394)

"Decode a string like '3[a2[c]]' → 'accaccacc'."

Insight: Two stacks — one for counts, one for strings. Push both when you see [. Pop and combine when you see ].

Variant 5: Largest Rectangle in Histogram (LC #84)

"Find the largest rectangle that fits in a histogram."

Insight: Monotonic increasing stack of bar indices. When a shorter bar is found, pop and calculate area using the current bar as the right boundary.

Variant 6: Score of Parentheses (LC #856)

"Calculate the score where () = 1, AB = A+B, and (A) = 2A."

Insight: Push 0 as a base score on (. On ), pop and either add 1 (if inner was 0) or double the inner score, then add to the new top.

When to Recognize the Stack Pattern

• "Matching" or "balanced" — brackets, tags, or any paired structure → push/pop matching
• "Next greater / smaller element" — monotonic stack, pop when condition is met
• "Previous greater / smaller element" — same pattern, scanning left to right
• "Nested structure" (decode, evaluate) — stack of states, push on open, pop on close
• "Undo / history" — browser back, file system path → stack of states

How to Actually Remember This

With 119 appearances across 48 companies including every major FAANG and finance firm, you cannot afford to blank on the stack approach for Valid Parentheses.

Tag all stack problems on DSAPrep.dev under Stack and Monotonic Stack. The spaced repetition system will resurface them at exactly the right intervals.

One problem at a time. One review at a time. Future you will thank present you.