ToolMight LogoToolMight
EasyStackPattern: Last-In First-Out (LIFO)Pattern: Bracket Matching

Valid Parentheses

Verify that code brackets (), {}, and [] are properly closed and nested in order. This is the exact algorithm compilers, linters, and IDEs use to detect syntax errors in real-time.

Problem Statement

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Examples & Constraints

Example 1
Input: s = "()[]{}"
Output: true
Explanation: Each bracket type opens and closes immediately in valid succession.
Example 2
Input: s = "(]"
Output: false
Explanation: The opening round parenthesis '(' is incorrectly closed by a square bracket ']'.
Constraints
  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

Stack Matching (LIFO)

Optimal Approach
Time:O(n)
Space:O(n)

Push opening brackets onto a stack. When encountering a closing bracket, pop the top element and verify it matches the expected bracket type.

Time ComplexityO(n)

We make a single pass through the string of length N. Stack pushes and pops take constant O(1) time.

Space ComplexityO(n)

In the worst case (e.g. '(((((('), the stack stores up to N opening characters simultaneously.

Underlying algorithmic logic

The Core Mental Model (Why a Stack?)

Brackets represent nested scopes—exactly like HTML tags (<div><span></span></div>) or nested function execution frames. You cannot close an outer scope while an inner scope is still active.

Crucially: the most recently opened bracket is always the first one that must be closed.
That "Last Opened, First Closed" behavior is the definition of LIFO (Last-In, First-Out), which makes a Stack the perfect data structure.

Step-by-Step Engineering Flow

  1. Early Parity Check (`O(1)` Fast Return): Every opening bracket demands a closing partner. If s.length is odd, a complete match is mathematically impossible. We can immediately return false before allocating any stack memory.
  1. Traverse and Match: Iterate through each character in the string:
  • Opening bracket ((, {, [): Push it onto the stack. We've opened a scope that expects a future closure.
  • Closing bracket (), }, ]):
  • Check if the stack is already empty. If yes, we have an orphan closing bracket with nothing to pair with (e.g., s = "]" ). Return false.
  • Pop the top opening bracket from the stack.
  • Compare: does the popped opener match the incoming closer? If there's a type mismatch (like ( paired with ]), return false.
  1. The Leftover Scope Trap: Never return true simply because the loop finished without an error! Consider s = "(((": no mismatched closers ever occurred, yet three brackets remain unclosed. Return stack.isEmpty()—only an empty stack guarantees all opened scopes were legitimately resolved.

Step-by-step execution walkthrough

1
Character '('

Encountered opening bracket. Push '(' onto the stack.

stack = ['(']
2
Character '['

Encountered nested opening bracket. Push '[' onto the stack.

stack = ['(', '[']
3
Character ']'

Encountered closer. Pop top element '['. Matches ']' -> scope resolved.

stack = ['(']
4
Character ')'

Encountered closer. Pop top element '('. Matches ')' -> scope resolved.

stack = []
5
Final Verification

String fully processed and stack is completely empty. Return true.

stack.isEmpty() -> true
Advantages
  • •Optimal single-pass O(n) runtime
  • •Directly mirrors compiler parsing & syntax highlight engines
  • •Early O(1) parity check rejects 50% of invalid cases before memory allocation
Trade-offs
  • •Requires O(n) auxiliary stack memory in worst-case nested strings

Code Implementations

Copy & paste production-ready solutions for Stack Matching (LIFO) in your language of choice

File: solution.py
Python
def is_valid(s: str) -> bool:
    # Fast exit: odd length cannot be fully balanced
    if len(s) % 2 != 0:
        return False
        
    stack: list[str] = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in bracket_map:
            # Closing bracket: pop top opener or sentinel '#' if stack is empty
            top = stack.pop() if stack else '#'
            if top != bracket_map[char]:
                return False
        else:
            # Opening bracket
            stack.append(char)
    # Valid only if stack is empty (no unclosed brackets)
    return len(stack) == 0
if __name__ == "__main__":
    print(f'is_valid("()[]{{}}"): {is_valid("()[]{}")}')
    print(f'is_valid("(]"): {is_valid("(]")}')
Interactive visualizer available

Understand Stack Visually

Learn the Last-In, First-Out (LIFO) stack data structure with pushing, popping, and structural queries. Test live edge cases and watch memory state transitions step-by-step.

Launch Stack Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyBinary Search
Visualizer

Binary Search

Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.

2 approaches(O(log n))
Learn logic
EasyLinked List
Visualizer

Reverse Linked List

Reverse the directional arrows of a singly linked list in-place. The classic test of reference manipulation and memory pointer management.

2 approaches(O(n))
Learn logic