#21 Easy Time O(n) Space O(n) Animated

Valid Parentheses

Determine if an input string of parentheses is valid.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern LIFO state for unresolved work

Keep only items whose matching decision has not been made yet.

Approach: Stack — Match Closing Brackets

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Keep only items whose matching decision has not been made yet.

Common Pitfall

Check that the stack is non-empty before reading its top.

Description

Determine if an input string of parentheses is valid.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Stack — Match Closing Brackets

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Read one item at a time.
Push unresolved work.
Match or remove work when its partner arrives.
Validate the final stack state.

def isValid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in s:
        if char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
        else:
            stack.append(char)
    return not stack

Min Stack

Valid Parentheses

Steps

Description

Constraints

Tags

Solution — Stack — Match Closing Brackets