Coding interview problems › Stack & Monotonic Stack

📚 Stack & Monotonic Stack Easy

Valid Parentheses

Valid Parentheses explained: push openers, pop on closers, and check the stack is empty at the end. Tested Python, common mistakes and a live stack visual.

Also searched as: balanced brackets problem · balanced parentheses using stack · check if brackets are balanced

📚

Try it live Free

Stacks & the Monotonic Stack

Start with the balanced-brackets mode: push the openers, pop on the closers, and watch a mismatched or leftover bracket fail the check.

Open the playground →

The problem

Given a string made only of the characters ()[]{}, decide whether it is balanced: every opening bracket is closed by the same type of bracket, and brackets close in the correct order.

Inputs = "{[()]}()"
OutputTrue
Inputs = "([)]"
OutputFalse

The ] arrives while ( is still the most recent open bracket.

The key insight

The bracket that must close next is always the most recently opened one that is still open. Last in, first out is exactly what a stack gives you: push every opener, and when a closer arrives it must match whatever is on top.

Brute force first: Repeatedly deleting adjacent pairs like () from the string until nothing changes works, but each pass is O(n) and there can be O(n) passes, so O(n²).

Step-by-step approach

  1. Make a map from each closer to its opener: ) to (, ] to [, } to {.
  2. Scan the string. Push every opening bracket onto a stack.
  3. For a closing bracket, if the stack is empty or its top is not the matching opener, return False; otherwise pop.
  4. After the scan, the string is valid only if the stack is empty.

Python solution

PYTHON 3tested
def is_valid(s):
    match = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in match:                     # a closer
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()
        else:                               # an opener
            stack.append(ch)
    return not stack                        # leftovers were never closed

Complexity

TimeO(n)
SpaceO(n)

Each character is pushed and popped at most once. In the worst case, a string of only openers, the stack holds all n characters.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n) time for a single pass and O(n) space for the stack in the worst case.

Can I solve it with counters instead of a stack?

Only when there is a single bracket type: then a counter that never goes negative and ends at zero is enough, with O(1) space. With several types you need the stack to check the order.

What if the string contains other characters, like letters?

Skip any character that is neither an opener nor a closer. The rest of the algorithm is unchanged.

Where else does this pattern appear?

Expression evaluation, HTML or XML tag matching, and undo histories all rely on the same last-opened, first-closed rule.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Stack & Monotonic Stack Stacks & the Monotonic Stack lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.