K AVAILABLE
OPEN TO WORK
← BACK TO KNOWLEDGE

KNOWLEDGE

Valid Parentheses: LIFO Stack Invariant

Master the Last-In First-Out bracket validation pattern to guarantee well-nested code, arithmetic parsing, and balanced delimiters.

Updated Sep 4, 20264 min readFoundationalData Structures & Algorithms

INTERACTIVE ALGORITHM WORKBENCH

Valid Parentheses Visualizer

EasyStack & StringsTime O(n)Space O(n)
String Stream (Input: "()[]{}")
Index012345
Char()[]{}

Scanner is at index 0 of 6

LIFO Stack
OPEN TOP (PUSH / POP) ↓
Stack is empty
Current Char—
Stack Top—
Stack Depth0
Sequence StatusScanning...
solution.py
1def is_valid(s: str) -> bool:
▶2    stack = []
3    pairs = {')': '(', ']': '[', '}': '{'}
4    for char in s:
5        if char in pairs:
6            top = stack.pop() if stack else '#'
7            if pairs[char] != top:
8                return False
9        else:
10            stack.append(char)
11    return len(stack) == 0
Step 1 of 8
WHY THIS STEP WORKS

A stack operates on Last-In, First-Out (LIFO). Whenever an opening bracket appears, we push it. When a closing bracket appears, the top element must match.

  1. 1Input string: "()[]{}"
  2. 2Initialize empty stack []
  3. 3Prepare to scan characters from left to right