What is the time and space complexity of Valid Parentheses?

The optimal solution runs in O(n) time and O(n) space.

Valid Parentheses: Stack

1. Understand the problem

Problem statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Input

A string `s` containing only the characters `(`, `)`, `{`, `}`, `[`, `]`.

Output

A boolean. `true` if every opening bracket is closed by the correct type in the right order, `false` otherwise.

Examples

input → s = "()"

output → true

input → s = "()[]{}"

output → true

Three separate valid pairs, none nested.

input → s = "(]"

output → false

The open paren is closed by a bracket, wrong type.

input → s = "([)]"

output → false

The brackets are interleaved incorrectly: [ is closed before ( is closed.

Quick check

Before any hints, take a guess.

"([)]" has 2 openers and 2 closers — the counts balance. But it's invalid: '[' was opened after '(' but closed before it. What structure tracks which opener is currently waiting?

Pick an answer to continue

2. Spot the pattern

Before any code, every problem starts with a question. For this problem:

“When I hit a closing bracket, how do I know which opener it belongs to?”

Imagine reading the string left to right. You see an opening bracket, okay, that'll need to close eventually. Then another opener. Now which one closes first? Whatever you opened most recently. If you kept a running list of openers as you go, the one on top is always the one waiting to close next. That structure, last in, first out, is a Stack.

Why not Counter?

A counter can track equal opens and closes but not order. The string ([)] has balanced counts but is invalid, a Stack catches this because it remembers which open bracket is waiting.

Quick check

The input is "([])". You've pushed '(' then '['. Now you hit ']'. Walk through what happens.

Pick an answer to continue

3. Brute force idea

Repeatedly scan the string and remove any directly-adjacent matched pair (like '()' or '[]'). Keep doing this until either the string is empty (valid) or you can't find any more pairs to remove (invalid).

Brute force (the slow one)

O(n²)

while '()' in s or '[]' in s or '{}' in s:
    s = s.replace('()', '')    # ← repeated scans and replacements
    s = s.replace('[]', '')
    s = s.replace('{}', '')

return s == ''

Why this is too slow

Each replacement pass is O(n) and you may need up to O(n) passes in the worst case, giving O(n²) total. The string also gets reallocated on every replacement.

Why this is not ideal for interviews

This approach works but it doesn't show understanding of the underlying pattern. Interviewers expect you to recognize that the last-opened bracket must be the first-closed, that's the LIFO behavior of a stack, and it solves this problem in a single O(n) pass.

Time: O(n²)

Space: O(n)

4. Climb the hint ladder

Five rungs. Click for the next one only when you genuinely need it. Each rung is a stronger nudge than the last.

5. The optimized approach

Walk through the string once. Push opening brackets onto a stack. When you hit a closing bracket, check if the stack's top is the matching opener, if yes, pop; if no (or stack is empty), return false. At the end, the stack should be empty.

Pseudocode

stack = []
pairs = {')': '(', ']': '[', '}': '{'}

for c in s:
    if c in '([{':
        stack.push(c)
    else:                            # c is a closing bracket
        if not stack or stack[-1] != pairs[c]:
            return false
        stack.pop()

return stack is empty

Quick check

Trace "([)]" through a counter-based approach: increment for openers, decrement for closers. Does it return valid or invalid?

Pick an answer to continue

6. Dry run, row by row

Trace it with the first example: s = "()".

step	char	action	stack after
1	(	push	['(']
2	[	push	['(', '[']
3	]	pop '['	['(']
4	)	pop '('	[]
5	—	end of string	empty

step 1: Opening bracket, push it.

step 2: Another opener, push.

step 3: Closing bracket. Top is '[' which matches ']', pop.

step 4: Closing bracket. Top is '(' which matches ')', pop.

step 5: Stack is empty, return true.

Quick check

Input: "((". The loop finishes without ever returning false — both characters just get pushed. Do you return true?

Pick an answer to continue

7. The code

You've seen the pseudocode and the dry run. Try writing the solution yourself in the editor on the right. Run your tests there first. The reveal stays here when you're ready to check.

8. Review & common mistakes

Lock it in

What is the signal that tells you to use the Stack pattern? Write it in one sentence, in your own words.

Common mistakes

Not checking whether the stack is empty before peeking
When you hit a closing bracket, always check `stack.length > 0` (or `bool(stack)` in Python) before looking at the top. If the stack is empty, there's no matching opener, that's an immediate false.
Forgetting to check the stack is empty at the end
A string like '((' passes every bracket check, each opener pushes fine, but the stack still has two unmatched openers at the end. Always verify `stack.length === 0` before returning true.
Using a counter instead of a stack
A single counter works for a single bracket type, but breaks with mixed types. '([)]' has balanced counts but isn't valid. You need the stack to track *which* bracket type is currently open.

Pattern family