LeetCode #20 Easy

Valid Parentheses

Given a string of ()[]{}, decide whether every bracket is closed by the correct type in the correct order.

stringstack

02

Intuition

💡

Brackets nest last-opened, first-closed — exactly a stack. Push each opener; when a closer arrives, the bracket on top must be its match. If not (or the stack is empty), it is invalid.

03

Approach

1

Repeatedly stripping pairs is slow

One correct idea is to keep deleting adjacent matched pairs — (), [], {} — until the string stops changing; if you end with nothing, it was valid. It works but each deletion rewrites the string, giving O(n²). The structure of the problem points at a data structure that handles nesting in linear time.

2

Brackets nest last-in, first-out — that's a stack

Valid brackets close in the reverse order they opened: the most recently opened bracket must be the next one closed. That 'most recent unmatched thing' is exactly what a stack tracks. Push every opening bracket; the top of the stack is always the only bracket a closer is allowed to match.

3

Match each closer against the top

Map each closing bracket to its required opener. On an opener, push it. On a closer, it's invalid if the stack is empty (nothing to close) or if the popped top isn't its matching opener (wrong type). After the scan, the string is valid only if the stack is empty — a leftover opener means something was never closed. One pass, O(n) time, O(n) space for the stack.

04

Solution & live demo

python

▶1class Solution:
▶2    def isValid(self, s):
▶3        pairs = {')': '(', ']': '[', '}': '{'}
▶4        stack = []
▶5        for ch in s:
▶6            if ch in pairs:
▶7                if not stack or stack.pop() != pairs[ch]:
▶8                    return False
▶9            else:
▶10                stack.append(ch)
▶11        return not stack

05

Edge cases

Wrong type, e.g. '(]'

The popped opener ( does not equal the expected [, so it returns false.

Closer with nothing open, e.g. ')'

Popping an empty stack is caught by the not stack check, returning false.

Leftover openers, e.g. '('

The loop ends with a non-empty stack, so not stack is false — correctly invalid.

06

Complexity

Time

O(n)

Space

O(n)

One pass; the stack can hold up to n openers (e.g. '((((').