DSA AnimatorDSA animations
Valid Parentheses LC #20 Easy Stack · Matching
Problem

Given a string s containing just the characters '(', ')', '[', ']', '{' and '}', determine if the input string is valid. An input string is valid if every open bracket is closed by the same type of bracket and in the correct order.

Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"
Output: true
Example 3
Input: s = "(]"
Output: false
Example 4
Input: s = "{[]}"
Output: true
Constraints: 1 ≤ s.length ≤ 10⁴  |  s consists of parentheses only ()[]{}
Try Examples
Custom:
Approach
Stack: push open brackets, pop & verify on close brackets
If stack is empty or mismatched on close → INVALID. If stack empty at end → VALID
Input String
Stack & Match Check
Stack (top→)
stack
empty
Match Check
— waiting for close bracket —
Variables
Index i
—
char
—
stack size
0
result
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
For each char: if open bracket ( [ { → push onto stack
2
If close bracket & stack is empty → return false (unmatched closer)
3
Pop top of stack; if it doesn't match current closer → return false
4
After loop: return stack.isEmpty() — true iff all opened brackets were closed
Time
O(n)
Space
O(n)
Why Stack Works

Stack mirrors nesting: the most recently opened bracket must be the first to close — LIFO is exactly the nesting order of brackets. Every time we hit a closer, the only valid matching opener is the one on top of the stack.

How to solve Valid Parentheses

LeetCode 20 · Easy · Stack · Pattern: Stack

Why the obvious approach is slow

Just counting opening and closing brackets is not enough. In the second example the counts match, but the order is wrong.

The key idea

The bracket opened last must be closed first. That is exactly how a stack works. When you see an opening bracket, push it. When you see a closing bracket, pop the top, and check that the pair matches. At the end, the stack must be empty.

Remember

Last opened, first closed, so use a stack. Push the expected closing bracket to make matching trivial.

Run the animation above on your own input, or watch the 1:37 video explanation of Valid Parentheses with a dry run and Java code.

More Stack problems