A complete visual walkthrough of the stack-based approach — from brute force to the elegant one-pass solution.
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Example 5:
Input: s = "([)]"
Output: false
Constraints:
1 <= s.length <= 104s consists of parentheses only '()[]{}'.The naive approach: repeatedly scan the string and remove any adjacent matching pairs (), {}, or []. Keep going until nothing changes. If the string becomes empty, it was valid.
This works, but each pass scans the entire string and we may need up to n/2 passes. That gives us O(n²) time in the worst case — far too slow for large inputs.
The problem with brute force: We're re-scanning the same characters over and over. What if we could process each character exactly once and remember what we've seen? That's where a stack comes in.
A stack is the perfect data structure for matching nested pairs. The rule is simple:
Here is the visual idea. Watch how the stack grows when we encounter opening brackets and shrinks when we find matching closing brackets:
Clever trick: Instead of pushing the opening bracket and then mapping to its pair later, we push the expected closing bracket. That way, when we see a closing bracket, we just check stack.pop() == c — no mapping table needed!
Let's trace through the input {[]} step by step, watching the stack at each stage.
Now let's see what happens with an invalid input: ([)]
Before coding, let's identify all the tricky inputs and how the stack handles them:
Quick optimization: If the string length is odd, return false immediately — you can never pair up an odd number of brackets. This avoids unnecessary work.
class Solution { public boolean isValid(String s) { // Use ArrayDeque as a stack (faster than Stack class) Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { // Opening bracket? Push the EXPECTED closing bracket if (c == '(') stack.push(')'); else if (c == '{') stack.push('}'); else if (c == '[') stack.push(']'); // Closing bracket? Pop and check for match // If stack is empty or top doesn't match → invalid else if (stack.isEmpty() || stack.pop() != c) return false; } // Valid only if all opening brackets were matched return stack.isEmpty(); } }
func isValid(s string) bool { // Use a slice as a stack stack := []byte{} for i := 0; i < len(s); i++ { c := s[i] // Opening bracket? Push the EXPECTED closing bracket if c == '(' { stack = append(stack, ')') } else if c == '{' { stack = append(stack, '}') } else if c == '[' { stack = append(stack, ']') } else { // Closing bracket? Pop and check for match // If stack is empty or top doesn't match → invalid if len(stack) == 0 || stack[len(stack)-1] != c { return false } stack = stack[:len(stack)-1] } } // Valid only if all opening brackets were matched return len(stack) == 0 }
def is_valid(s: str) -> bool: # Use a list as a stack stack: list[str] = [] for c in s: # Opening bracket? Push the EXPECTED closing bracket if c == '(': stack.append(')') elif c == '{': stack.append('}') elif c == '[': stack.append(']') # Closing bracket? Pop and check for match # If stack is empty or top doesn't match → invalid elif not stack or stack.pop() != c: return False # Valid only if all opening brackets were matched return len(stack) == 0
impl Solution { pub fn is_valid(s: String) -> bool { // Use a Vec as a stack let mut stack: Vec<char> = Vec::new(); for c in s.chars() { // Opening bracket? Push the EXPECTED closing bracket match c { '(' => stack.push(')'), '{' => stack.push('}'), '[' => stack.push(']'), // Closing bracket? Pop and check for match // If stack is empty or top doesn't match → invalid _ => if stack.pop() != Some(c) { return false; } } } // Valid only if all opening brackets were matched stack.is_empty() } }
function isValid(s: string): boolean { // Use an array as a stack const stack: string[] = []; for (const c of s) { // Opening bracket? Push the EXPECTED closing bracket if (c === '(') stack.push(')'); else if (c === '{') stack.push('}'); else if (c === '[') stack.push(']'); // Closing bracket? Pop and check for match // If stack is empty or top doesn't match → invalid else if (stack.length === 0 || stack.pop() !== c) return false; } // Valid only if all opening brackets were matched return stack.length === 0; }
Why push the closing bracket? By pushing the expected closing bracket instead of the opening one, the matching logic becomes a simple equality check: stack.pop() != c. No need for a separate Map or switch statement to look up pairs.
Enter any bracket string and step through the algorithm one character at a time. Watch the stack grow and shrink in real time.
We process each character exactly once in a single pass, giving O(n) time. In the worst case (all opening brackets like "((((("), the stack holds all n characters, so space is O(n).
Repeatedly scan the string to remove adjacent matching pairs like "()", "[]", "{}". Each scan is O(n) and up to n/2 passes may be needed before the string is empty or no more pairs remain, giving O(n2). The mutable string copy uses O(n) space.
A single pass pushes expected closing brackets onto a stack for each opener, and pops to verify each closer. Each character triggers exactly one push or one pop, giving O(n) time. The stack stores at most n/2 elements (all openers), so space is O(n).
The stack ensures LIFO matching. The most recently opened bracket must be the first one closed — this is exactly what a stack enforces. You cannot beat O(n) time since every character must be inspected, and O(n) space is unavoidable because the nesting order must be remembered. Early exits on odd length and first mismatch mean we often use far less in practice.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.