What is the brute force approach and complexity for Valid Parentheses?

Repeatedly delete "()", "[]", "{}" until nothing changes with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Valid Parentheses?

Push openers; each closer must match and pop the top with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Valid Parentheses?

Look for key signals in the prompt: "closed by the same type" indicates Each closer must be compared with a specific opener → we need to remember the openers, not just count them.; "closed in the correct order" indicates The last bracket opened must be the first one closed → last in, first out → stack.; "every close bracket has a matching open" indicates Check for an empty stack before popping, and for leftovers at the end..

Valid Parentheses

Easy·LeetCode #20Basic Anchor

LeetCode

Jump:

30-Second Mental ModelStack — Matching / nesting

Complexity:O(N²)→O(N)

Key Insight

Read the string once. Every open bracket waits on a stack. A close bracket must match the bracket on top of the stack, which is the most recent one still open. If it matches, pop it: that pair is done. At the end, the stack must be empty.

Core Validity Invariant

A closer is allowed only if the stack is not empty and its top is the same type of opener. The whole string is valid only if every closer passed this test and the stack is empty at the end.

Problem

You are given a string s made only of the six bracket characters (, ), [, ], { and }.

Return true if the brackets are valid, otherwise false. The string is valid when:

every open bracket is closed by a bracket of the same type,
brackets are closed in the right order (the one opened last is closed first),
every close bracket has an open bracket before it to match.

Input

A string s of bracket characters.

Output

true if every bracket is matched correctly, otherwise false.

Example 1

Input: s = "()"

Output: true

One pair, opened and closed.

Example 2

Input: s = "()[]{}"

Output: true

Three pairs, one after another.

Example 3

Input: s = "(]"

Output: false

The ( is closed by a ], which is the wrong type.

Example 4

Input: s = "([])"

Output: true

The [] sits fully inside the (). The inner pair closes first, then the outer one.

Example 5

Input: s = "([)]"

Output: false

The ( is closed while the [ opened after it is still open. The pairs cross instead of nesting.

Constraints

• 1 ≤ s.length ≤ 10^4
• s contains only the characters ()[]{}

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
When I read a closing bracket, which open bracket is it supposed to close?
2.
Is that always the first open bracket, or the most recent one that is still open?
3.
Would counting how many of each type are open be enough? Try "([)]".
4.
What should happen if a closing bracket arrives and nothing is open?
5.
When I reach the end of the string, what must be true about the open brackets?

Brute force approach

Idea

A valid string always has at least one pair like (), [] or {} sitting side by side (the innermost one). Delete all such pairs. That exposes new side-by-side pairs, so repeat. If the string becomes empty, it was valid. If a round deletes nothing and something is left, it was not.

Thinking process

1
Look at "{[()]}". The () in the middle is a complete pair with nothing inside it.
2
Removing a complete pair cannot break or fix anything around it, so delete it: "{[]}".
3
Now [] is side by side. Delete it, then {}. The string is empty, so it was valid.
4
For "([)]" there is no side-by-side pair at all, so nothing can be deleted and the answer is false.

Visual

Red cells are the pairs deleted in this round. Each round rescans everything that is left.

Delete pairs, round by rounds = "{[()()]}"step 1/4

round 1

{

[

(

)

(

)

]

}

after

{

[

]

}

Work

pairs deleted: 2
characters scanned so far: 6
length left: 4

Round 1: scanned all 8 chars to delete 2 pairs

Scan the whole string and delete every side-by-side pair. The characters around them were read again for nothing.

Code & Implementation

brute.cpp

class Solution {
public:
    bool isValid(string s) {
        // In a valid string, some "()", "[]" or "{}" always sits side by side.
        // Delete every such pair, and repeat until a round deletes nothing.
        bool changed = true;
        while (changed) {
            changed = false;
            string next;
            for (int i = 0; i < (int)s.size(); i++) {
                if (i + 1 < (int)s.size()) {
                    char a = s[i], b = s[i + 1];
                    if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')) {
                        i++;            // skip both characters of the pair
                        changed = true;
                        continue;
                    }
                }
                next += s[i];
            }
            s = next;
        }
        // Valid exactly when everything got deleted.
        return s.empty();
    }
};

class Solution {
    public boolean isValid(String s) {
        // In a valid string, some "()", "[]" or "{}" always sits side by side.
        // Delete every such pair, and repeat until a round deletes nothing.
        boolean changed = true;
        while (changed) {
            changed = false;
            StringBuilder next = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if (i + 1 < s.length()) {
                    char a = s.charAt(i), b = s.charAt(i + 1);
                    if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')) {
                        i++; // skip both characters of the pair
                        changed = true;
                        continue;
                    }
                }
                next.append(s.charAt(i));
            }
            s = next.toString();
        }
        return s.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        # In a valid string, some "()", "[]" or "{}" always sits side by side.
        # Delete every such pair, and repeat until a round deletes nothing.
        changed = True
        while changed:
            changed = False
            next_s = []
            i = 0
            while i < len(s):
                if i + 1 < len(s):
                    pair = s[i:i + 2]
                    if pair in ("()", "[]", "{}"):
                        i += 2  # skip both characters
                        changed = True
                        continue
                next_s.append(s[i])
                i += 1
            s = "".join(next_s)

        # Valid exactly when everything got deleted.
        return len(s) == 0

export function isValid(s: string): boolean {
    // In a valid string, some "()", "[]" or "{}" always sits side by side.
    let changed = true;
    while (changed) {
        changed = false;
        let next = "";
        for (let i = 0; i < s.length; i++) {
            if (i + 1 < s.length) {
                const a = s[i];
                const b = s[i + 1];
                if ((a === "(" && b === ")") || (a === "[" && b === "]") || (a === "{" && b === "}")) {
                    i++; // skip pair
                    changed = true;
                    continue;
                }
            }
            next += s[i];
        }
        s = next;
    }
    return s.length === 0;
}

Complexity

Time O(N²)Space O(N)

Each round scans the whole string, and a deeply nested string like ((((...)))) loses only one pair per round. That is up to n / 2 rounds of n work each: about 5·10^7 steps for n = 10^4.

Optimized approach

Idea

Start from brute force

Brute force deletes the innermost pairs, then scans the whole string again to find the next innermost pairs.

Find the repeated work

Every round re-reads characters that were already checked and are just waiting for their partner. The only bracket that can be closed next is the most recent open one, so all that rescanning is wasted.

Define the state — what variables do I need?

st: The open brackets that are still waiting for their closer, oldest at the bottom, newest on top.
c: The character being read right now.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

c is an opener: ( [ {

st.push(c)

It cannot be checked yet. It has to wait until its closer arrives, and anything opened after it must close first.

c is a closer and the stack is empty

return false

There is no open bracket for it to close, e.g. )(.

c is a closer and st.top() is a different type

return false

The most recent open bracket must close first. Closing any other one would make pairs cross, like ([)].

c is a closer and st.top() matches

st.pop()

This pair is complete. The bracket below it becomes the most recent open one.

After the loop

return st.empty()

Anything still on the stack was opened but never closed, e.g. ((.

What does the current window add to the answer?

Each pop closes exactly one pair. When the string ends with an empty stack, every bracket has been paired with the right partner.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;   // openers that are still waiting for their closer

        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                // A closer with nothing open, e.g. ")(".
                if (st.empty()) return false;
                char top = st.top();
                st.pop();
                // The closer must match the MOST RECENT open bracket.
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false;
            }
        }
        // Openers left over were never closed, e.g. "((".
        return st.empty();
    }
};

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

class Solution {
    public boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>(); // openers waiting for their closer

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                // A closer with nothing open
                if (st.isEmpty()) return false;
                char top = st.pop();
                // The closer must match the most recent open bracket
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return st.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        st = []  # openers that are still waiting for their closer
        matching = {')': '(', ']': '[', '}': '{'}

        for c in s:
            if c in ('(', '[', '{'):
                st.append(c)
            else:
                # A closer with nothing open
                if not st or st.pop() != matching[c]:
                    return False

        # Openers left over were never closed
        return len(st) == 0

export function isValid(s: string): boolean {
    const st: string[] = []; // openers that are still waiting for their closer
    const matching: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === "(" || c === "[" || c === "{") {
            st.push(c);
        } else {
            // A closer with nothing open
            if (st.length === 0) return false;
            const top = st.pop();
            if (top !== matching[c]) return false;
        }
    }
    // Openers left over were never closed
    return st.length === 0;
}

Complexity

Time O(N)Space O(N)

Each character is pushed at most once and popped at most once. In the worst case (all openers) the stack holds all n characters. A quick extra check: if n is odd, the answer is always false.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Repeatedly delete "()", "[]", "{}" until nothing changes	O(N²)	O(N)
Optimal	Push openers; each closer must match and pop the top	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“closed by the same type”Each closer must be compared with a specific opener → we need to remember the openers, not just count them.
“closed in the correct order”The last bracket opened must be the first one closed → last in, first out → stack.
“every close bracket has a matching open”Check for an empty stack before popping, and for leftovers at the end.

Pairs that open and close+inner pairs close before outer ones+the newest unmatched item is the only one that can match next→Stack — Matching / nesting

This is the anchor of the sub-pattern: openers wait on the stack until their closer arrives, and a closer only ever looks at the top. Later questions keep this exact move but change what sits on the stack: the answer string itself (Remove Adjacent Duplicates), indices (Minimum Remove), or saved state for each level of nesting (Decode String).

Don't make this mistake

Forgetting to check the stack is empty at the end

✗ for (char c : s) { ... } return true;

✓ return st.empty();

For "((" every character is an opener, so no check inside the loop ever fails. The two openers are still waiting at the end, so the answer must be false.

Popping or reading the top of an empty stack

✗ char top = st.top(); // when s starts with ')' st.pop();

✓ if (st.empty()) return false; char top = st.top(); st.pop();

For ")" the stack is empty when the closer arrives. Calling top() or pop() on an empty std::stack is undefined behaviour and usually crashes. A closer with nothing open is simply invalid.

Using a counter instead of a stack (pattern confusion)

✗ int open = 0; for (char c : s) { if (c == '(' || c == '[' || c == '{') open++; else if (--open < 0) return false; } return open == 0;

✓ stack<char> st; // remember WHICH brackets are open, in order

A single counter works when there is only one type of bracket. With three types it says yes to "([)]": the count goes 1, 2, 1, 0. Even one counter per type fails here, because the problem is the order: the ) arrives while [ is the most recent open bracket. Only a stack remembers that order.

Comparing the closer with the first opener instead of the latest

Matching each closer with the earliest open bracket (like a queue) accepts "([)]" and rejects "([])". Inner brackets close first, so the partner is always the most recent opener: the top of the stack.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Expression Parser & Interpreter Pattern

Abstract syntax tree evaluation and operator precedence parsing.

Explore Track

C++ Internals

Stack vs Heap Segments

Call stack frame layout, return addresses, and buffer overflow prevention.

Explore Track

Remove All Adjacent Duplicates In String