Blind 75 Visualized

#24 · Stack

Valid Parentheses

Given a string containing only '(', ')', '{', '}', '[' and ']', determine whether it is valid: every bracket is closed by the same type, in the correct order.

EasyLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Stack (last in, first out)

A stack only exposes its top: push adds to it and pop removes from it. Brackets nest, so the most recently opened bracket is always the next one that has to close: exactly the order a stack gives back.

Memory layout

Usually a dynamic array with a top index: push and pop touch only the end, so they are O(1) amortized and cache friendly. A linked-list stack allocates per element.

OperationCost
push / pop / peekO(1)
validate a stringO(n) time, O(n) worst-case space

Closer-to-opener lookup

A tiny table (or a switch) relating each closing bracket to its opener, or each opener to its closer, so adding a new bracket type does not add another branch.

Memory layout

Three fixed entries; fits in registers or a single cache line.

OperationCost
lookupO(1)

Why it fits

  • Valid nesting is a last-opened-first-closed discipline. A stack remembers exactly the unclosed openers in the order they must be closed.
  • Each character is pushed at most once and popped at most once, so the whole check is a single left-to-right pass: O(n).
  • The stack is also the proof of correctness: it is empty at the end if and only if every opener found its closer.

Why alternatives degrade

One counter per bracket type:
Counts catch "( ]" style imbalance but not interleaving: "([)]" has balanced counts and is invalid. Order matters, and counters forget it.
A single counter:
Works for one bracket type only; with several types it cannot tell which type to close.
Repeatedly deleting "()", "[]", "{}":
Correct but every round is a full pass and creates new strings: O(n²).
Regular expressions:
Nested balanced brackets are not a regular language; a regex cannot count nesting depth.

Four approaches, from naive to production

1 · beginner

Delete adjacent pairs until stuck

time O(n²)space O(n)

A valid string always contains an adjacent "()", "[]" or "{}". Remove all such pairs, repeat until nothing changes, and check whether the string became empty.

bool isValid(string s) {
    string prev;
    auto removeAll = [](const string& str, const string& pat) {
        string r;
        for (size_t i = 0; i < str.size();) {
            if (str.compare(i, 2, pat) == 0) i += 2;
            else r += str[i++];
        }
        return r;
    };
    while (s != prev) {
        prev = s;
        s = removeAll(removeAll(removeAll(s, "()"), "[]"), "{}");
    }
    return s.empty();
}

Flaws & bottlenecks

  • Each round scans and rebuilds the whole string, and up to n/2 rounds are needed for deeply nested input like "((((...))))".
  • Allocates a new string per replacement.
  • Gives no information about where the first error is.

Interviewer cross-questions

Why does repeated deletion work?

Say: In a valid string the innermost bracket pair is always adjacent. Deleting it leaves a smaller valid string, so repeating empties the string. If the string is invalid, some bracket never becomes adjacent to its partner and survives.

What is the worst case?

Say: A fully nested string such as "((((....))))" removes only one layer per round, so about n/2 rounds of O(n) work each: O(n²).

How do you do it in one pass?

Say: A stack. Push openers and, on a closer, pop and compare. That deletes the innermost pair at the moment it appears.

2 · intermediate

Stack with comparison chain

time O(n)space O(n)

Push every opening bracket. On a closing bracket, pop the stack and check that the popped opener is the matching type. The string is valid if the stack ends empty.

bool isValid(string s) {
    vector<char> stack;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push_back(c);
        } else {
            bool had = !stack.empty();
            char top = 0;
            if (had) { top = stack.back(); stack.pop_back(); }
            if (top == '(' && c != ')') return false;
            if (top == '[' && c != ']') return false;
            if (top == '{' && c != '}') return false;
            if (!had) return false;
        }
    }
    return stack.empty();
}

Flaws & bottlenecks

  • One comparison line per bracket type: adding "<>" means another branch and another chance for a typo.
  • Popping an empty stack has to be handled separately (the extra check on the last comparison line).
  • The order of the checks matters and is easy to get wrong.

Interviewer cross-questions

What if the stack is empty when a closer arrives?

Say: There is no opener for it, so the string is invalid. The code must check for the empty case explicitly before relying on the popped value.

Why must the stack be empty at the end?

Say: A non-empty stack means some opener never saw its closer, e.g. "((" or "(()".

How can you remove the repeated branches?

Say: Use a closer-to-opener table, or push the expected closer instead of the opener.

3 · advanced

Stack + lookup table

time O(n)space O(n)

Same stack, but a table maps each closing bracket to its opener. A closer pops and compares to table[closer]; anything not in the table is an opener and is pushed.

bool isValid(string s) {
    unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    vector<char> stack;
    for (char c : s) {
        if (pairs.count(c)) {
            if (stack.empty() || stack.back() != pairs[c]) return false;
            stack.pop_back();
        } else {
            stack.push_back(c);
        }
    }
    return stack.empty();
}

Flaws & bottlenecks

  • Any character that is not a closer is pushed as an opener, so garbage input such as "a" is silently accepted as an opener.
  • The pop of an empty stack must compare unequal to every possible opener: this works only because the empty-pop value differs from every bracket.
  • Still O(n) memory for strings of openers only, like "((((((".

Interviewer cross-questions

What if the input contains other characters?

Say: Decide with the interviewer. Either ignore them (skip anything that is neither opener nor closer) or reject them. As written they are treated as openers and will leave the stack non-empty, which makes the result false.

Can you reduce the stack memory?

Say: Not in general: a string of n/2 openers followed by n/2 closers needs depth n/2. You can bail out early when the pending openers exceed the characters left, which is the expert approach.

Why a table over if/else?

Say: It is data, not logic: new bracket types are one entry, there is a single comparison to test, and it is hard to forget a case.

4 · expert

Push the expected closer + prune

time O(n)space O(n)

Push the closing bracket each opener expects, so a closer is checked with one equality test. Reject odd lengths up front and stop as soon as the pending closers outnumber the remaining characters.

bool isValid(string s) {
    if (s.size() % 2 == 1) return false;
    vector<char> stack;
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (c == '(') stack.push_back(')');
        else if (c == '[') stack.push_back(']');
        else if (c == '{') stack.push_back('}');
        else if (stack.empty() || stack.back() != c) return false;
        else stack.pop_back();
        if ((int)stack.size() > (int)s.size() - 1 - i) return false;
    }
    return stack.empty();
}

Flaws & bottlenecks

  • The expected-closer trick is less obvious to readers than pushing the opener.
  • Pruning helps only on invalid inputs (valid input still reads every character).
  • Still O(n) space in the worst case; the stack depth is inherent to the problem.

Interviewer cross-questions

Why push the closer instead of the opener?

Say: The closing check becomes "popped value equals the current character", with no table and no branch per type. Unknown characters fail the same test, so invalid input is rejected for free.

Why can an odd length be rejected immediately?

Say: Every opener is matched with exactly one closer, so valid strings have even length.

What does the pruning check prove?

Say: If there are more pending closers than characters left to read, even a perfect tail could not close them all, so the answer is already false. It saves work on strings like "((((((((" early.

Synchronized code walkthrough

Showing: Delete adjacent pairs until stuck — shares the player above; click any step to jump.

bool isValid(string s) {
    string prev;
    auto removeAll = [](const string& str, const string& pat) {
        string r;
        for (size_t i = 0; i < str.size();) {
            if (str.compare(i, 2, pat) == 0) i += 2;
            else r += str[i++];
        }
        return r;
    };
    while (s != prev) {
        prev = s;
        s = removeAll(removeAll(removeAll(s, "()"), "[]"), "{}");
    }
    return s.empty();
}