Skip to content

Balanced Parentheses Checker

1/14

How do you check if parentheses are balanced?

A string of brackets is balanced when every opening bracket — (, [ or { — is closed by the matching closing bracket in the correct order. Check it with a stack: push every opener, and for every closer pop the top and confirm it is the matching opener. The string is balanced only if no check fails and the stack is empty at the end, which takes O(n) time.

How it works

  1. Start with an empty stack and scan the string from left to right, ignoring characters that are not brackets.
  2. On an opening bracket (, [ or {, push it.
  3. On a closing bracket, if the stack is empty the closer has no partner — not balanced.
  4. Otherwise pop the top. If it is not the matching opener (for example [ popped for a )), the brackets cross — not balanced.
  5. After the last character the string is balanced only if the stack is empty; anything left is an opener that was never closed.

Why a stack?

Brackets nest: whatever was opened last must be closed first. { [ ( ) ] } closes in the reverse order it opened, which is exactly last in, first out. The stack holds the openers that are still waiting, and its top is always the one the next closer has to match.

With a single kind of bracket you don't even need a stack — a counter does the job (see below). The stack becomes necessary as soon as there are several kinds, because a counter can't tell ([)] from ([]).

Worked example: {[()()]}

  • { → push. Stack: {
  • [ → push. Stack: { [
  • ( → push. Stack: { [ (
  • ) → pop (, which matches. Stack: { [
  • ( → push. Stack: { [ (
  • ) → pop (, match. Stack: { [
  • ] → pop [, match. Stack: {
  • } → pop {, match. Stack: empty

Every closer matched and the stack ended empty, so {[()()]} is balanced. Eight characters, eight O(1) stack operations: the algorithm is O(n) time, and O(n) space in the worst case — a string made only of openers.

The three ways a string can be unbalanced

  • Crossed brackets — ([)]: after pushing ( and [, the ) pops [. The pair doesn't match, so the brackets overlap instead of nesting.
  • A closer with nothing open — )( or ()): the stack is empty when a closing bracket arrives.
  • An opener that is never closed — ((): the scan finishes with ( still on the stack.

A correct checker must catch all three, and most buggy solutions miss one. Try each in the visualizer above: the failing bracket and its partner turn red and the explanation says which rule was broken.

Counter vs stack

With only one bracket type, keep an integer depth: add 1 on (, subtract 1 on ), fail immediately if it goes negative, and require depth == 0 at the end. That uses O(1) space.

With several types a counter breaks down. In ([)] every per-type count stays non-negative and ends at zero, yet the brackets cross. Only a stack remembers the order in which the brackets were opened.

Common mistakes

  • Popping without first checking for an empty stack — crashes on inputs like ).
  • Returning true after the loop without checking that the stack is empty — accepts ((.
  • Using one counter for all bracket types — accepts ([)].
  • Hard-coding the pairs in a chain of if statements and mismatching one; a map from each closer to its opener avoids typos.
  • Rejecting other characters: code such as if (a[i] == f(x)) { … } should be checked by skipping non-bracket characters.
  • Using the odd-length shortcut (len(s) % 2 == 1 → false) when the input can contain characters other than brackets.

Interview variations

  • Valid Parentheses (LeetCode 20): exactly this algorithm.
  • Minimum Add to Make Parentheses Valid (921): count unmatched ( and unmatched ); no stack needed.
  • Minimum Remove to Make Valid Parentheses (1249): keep a stack of the *indices* of unmatched brackets, then delete them.
  • Longest Valid Parentheses (32): a stack of indices seeded with −1; after each match the current valid length is i - top.
  • Generate Parentheses (22): backtracking that never lets closers outnumber openers.
  • Valid Parenthesis String with * wildcards (678): track the range of possible open counts.

HTML and XML validators use the same idea with tags in place of single characters.

Time and space complexity

CaseTimeSpaceWhy
Stack algorithmO(n)O(n)Each bracket is pushed and popped at most once; worst case, every opener stays on the stack.
Counter (one bracket type)O(n)O(1)Only the nesting depth is stored.
Early failure at position kO(k)O(k)The scan stops at the first mismatch or unmatched closer.

Balanced Parentheses in Python

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)          # push
        elif ch in ")]}":
            if not stack:
                return False          # nothing open
            top = stack.pop()
            if top != pairs[ch]:
                return False          # crossed, e.g. "([)]"
    return not stack                  # all closed?


# is_balanced("{[()()]}")  -> True
# is_balanced("([)]")      -> False

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Which data structure is used to check balanced parentheses?

A stack. The most recently opened bracket must be closed first, and a stack gives exactly that last-in, first-out access.

What is the time complexity of checking balanced parentheses?

O(n) time for a string of length n, because each character is examined once and pushed or popped at most once, plus O(n) extra space for the stack in the worst case.

Why is ([)] not balanced?

Because the brackets cross: [ opens after (, so it has to close before ). When ) arrives the top of the stack is [, which doesn't match.

Is an empty string balanced?

Yes. It has no unmatched brackets and the stack is empty at the end, so the algorithm returns true.

Can you check balanced parentheses without a stack?

For a single bracket type, yes: a counter that never drops below zero and ends at zero is enough. For mixed types you need a stack — or recursion, which uses the call stack.

How do you check balanced brackets in Python?

Loop over the string, append openers to a list, and on a closer pop the list and compare it with a dictionary of pairs; return not stack at the end. The full function is shown above.

Keep learning

Last updated