Algorithm

Valid Parentheses

Stacks & Queues Pattern

Valid Parentheses

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

CONSTRAINTS
  • 1 <= s.length <= 10⁴
  • s consists of parentheses only: ()[]{}
  • A valid string always has even length (every open needs one close)
EXAMPLE 1
Input: s = "()"
Output: true
Single matching pair.
EXAMPLE 2
Input: s = "()[]{}"
Output: true
Three independent pairs in sequence — no nesting.
EXAMPLE 3
Input: s = "{[()]}"
Output: true
Correct nesting: innermost () closes first, then [], then {}.
EXAMPLE 4
Input: s = "(]"
Output: false
Open '(' cannot be closed by ']'. Type mismatch.
What if the string is empty?
An empty string has no unmatched brackets and is valid. The stack will be empty at the start and remains empty — return true.
Can the string have an odd number of characters?
An odd-length string can never be valid — every open bracket needs exactly one close bracket. You can return false immediately if s.length is odd.

When you need to ensure that every opening bracket is closed in the correct order, a beginner might first try to just count the brackets. If there are three '(' and three ')', it is valid, right?

Wrong! Consider the string ([)]. The counts are perfect, but the logic is broken. Brackets are like nested boxes: if you open a large box '(' and then a small box '[', you must close the small box before you can even touch the large one. This strict nesting means only the most recently opened bracket matters at any given moment.

This is why we need a Stack. A Stack is a Last-In, First-Out (LIFO) data structure. It acts like a temporary memory that only remembers the very last promise you made.

The LIFO Promise

- Making a Promise: Every time you see an opening bracket ('(', '[', '{'), you are making a promise to close it later. You Push this promise onto the Stack.
- Fulfilling a Promise: When you see a closing bracket (')', ']', '}'), you are checking the most recent promise you made. You Pop the top of the Stack.
- If the brackets match (e.g., you see a ')' and the top of the Stack is '('), the promise is fulfilled!
- If they do not match, or the Stack is empty (meaning you are trying to close a box you never opened), the string is invalid.
- The Final Audit: Once you have scanned the whole string, the Stack must be completely empty. If there is a promise left over, it means you opened a box and forgot to close it.

Code Blueprint
text
stack = []
bracket_map = { ')': '(', ']': '[', '}': '{' }

FOR each character in string:
    IF character is an OPENING bracket:
        stack.PUSH(character)
    ELSE (it's a CLOSING bracket):
        IF stack is empty OR stack.POP() != bracket_map[character]:
            RETURN False (Invalid Order)

RETURN stack.IS_EMPTY (Valid only if all closed)
Worked Example:{[()]}
0
{
Top
Scan '{': It is an opening bracket, so we push it onto the stack. Stack = ['{'].
0
{
1
[
Top
Scan '[': Another opener. Push onto the stack. Stack = ['{', '['].
0
{
1
[
2
(
Top
Scan '(': Innermost opener. Push onto the stack. Stack = ['{', '[', '('].
0
{
1
[
Top
Scan ')': A closing bracket. Peek stack top ('('). It is a match! Pop it. Stack = ['{', '['].
0
{
Top
Scan ']': Closing bracket. Peek stack top ('['). Match! Pop it. Stack = ['{'].
Scan '}': Closing bracket. Peek stack top ('{'). Match! Pop it. Stack is empty. All brackets matched successfully!
Interactive Strategy Visualization
BALANCED STRUCTURE INSIGHT

Last-In-First-Out Verification

{
[
]
}
Balance Stack
Current State
?
Processing segment...
Execution Trace

Start with an empty stack.

The Symmetry Principle

A stack naturally ensures that the most recently opened context is the first to be closed.

O(N²) Repeatedly Strip Pairs
→
O(N) One Pass · O(N) Stack of Open Brackets