Valid Parentheses — Stack Approach

What does it solve?

Given a string of brackets ( ) { } [ ], determine whether it is valid — meaning every opening bracket is closed by the correct type in the correct order, and no bracket is left unmatched.

A stack is the perfect tool: push opening brackets, and when a closing bracket arrives, check that it matches the top of the stack.

The core idea

// for each char in string:
if opening bracket: stack.push(char)
else: // closing bracket
  if stack empty OR top doesn't match:
    return false
  stack.pop()
return stack.empty()

Complexity

Time complexity

O(n)

Each character is pushed or popped from the stack at most once — one pass through the string.

Space complexity

O(n)

In the worst case (all opening brackets), the stack holds all n characters.

Examples & edge cases

Live animation

current char pushed to stack matched & popped mismatch / invalid

Stack (top → left)

Step — of —

Stack size

—

Current char

—

Action

—

Result

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Char	Action	Stack top	Stack	Status

C++ implementation

valid_parentheses.cpp

#include <bits/stdc++.h>
using namespace std;

bool isValid(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);            // opening bracket — always push
        } else {
            if (st.empty()) return false;   // nothing to match
            char top = st.top(); st.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }
    return st.empty();     // unmatched opening brackets would remain
}

int main() {
    cout << isValid("({[]})") << "\n";  // 1
    cout << isValid("([)]")  << "\n";  // 0
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars