-
Notifications
You must be signed in to change notification settings - Fork 0
051 — Valid Parentheses
LeetCode 20 · Easy. Given a string s containing just the characters (, ), {, }, [, and ], determine if the input string is valid. A string is valid if every open bracket is closed by the same type of bracket, and open brackets are closed in the correct order.
Picture folding a letter into an envelope, then that envelope into a bigger envelope, then that into a box. To unpack, you must open the box first, then the outer envelope, then the inner one — last thing sealed in is the first thing you're allowed to open back up. If you ever try to pull the inner envelope out before opening the box around it, something's wrong — the nesting has been violated.
Brackets work the same way. Every open bracket is a "sealing" step, and every close bracket must undo the most recent still-open seal, not some older one. The moment a closing bracket doesn't match the most recently opened bracket, the string can't be validly nested — no amount of further characters can fix it.
"Valid parentheses" / "balanced brackets" / "every opening bracket must be closed by the same type in the correct order" is the canonical signal for a stack: whenever the rule is "the most recently opened thing must be the first thing closed," you need last-in-first-out bookkeeping. This problem uses a stack directly, not the monotonic (increasing/decreasing) invariant that gives the pattern its name — it's the same LIFO intuition underneath, just without the "discard dominated elements" twist that defines a true monotonic stack.
A candidate reaching for string manipulation first might repeatedly delete the innermost matched pair — "()", "[]", or "{}" — until nothing more can be removed, then check whether the whole string vanished.
import Foundation
func isValidBruteForce(_ s: String) -> Bool {
var str = s
let pairs = ["()", "[]", "{}"]
var changed = true
while changed {
changed = false
for pair in pairs {
if let range = str.range(of: pair) {
str.removeSubrange(range)
changed = true
}
}
}
return str.isEmpty
}Big-O: O(n²) time — each of up to n / 2 removal passes scans and mutates a string of length up to n. O(n) space for the mutable copy of s.
Walk the string once. Push every open bracket. On a closing bracket, it must match whatever is currently on top of the stack — if it doesn't (or the stack is empty), the string is invalid immediately.
func isValid(_ s: String) -> Bool {
var stack: [Character] = []
let closingToOpening: [Character: Character] = [")": "(", "]": "[", "}": "{"]
for char in s {
if char == "(" || char == "[" || char == "{" {
stack.append(char)
} else if let expectedOpen = closingToOpening[char] {
if stack.popLast() != expectedOpen {
return false
}
}
}
return stack.isEmpty
}
// smoke test
print(isValid("()[]{}")) // true
print(isValid("(]")) // false
print(isValid("([)]")) // false
print(isValid("{[]}")) // trueBig-O: O(n) time — a single pass, O(1) work per character. O(n) space for the stack in the worst case (an all-opening-bracket string).
The brute force repeatedly re-scans the entire string looking for any innermost matched pair, which throws away all the positional information it already has each time it starts a new pass. The optimal solution recognizes that validity only ever depends on the single most recently opened, still-unclosed bracket — everything older is irrelevant until that one is resolved. A stack is exactly the structure that keeps "the most recent still-open thing" instantly accessible at the top, turning a string-rewriting search into one linear pass where every character is looked at exactly once.
- Stacks — the LIFO discipline this solution implements directly: push on open, pop-and-compare on close.
- Monotonic Stack — not a genuine match here (there's no increasing/decreasing invariant being maintained), but it's the closest pattern-family chapter in this wiki, and it builds on the same "last in, first out" foundation as this plain-stack solution.
- Arrays & Strings — the string being scanned character by character.
Valid Parentheses is nested envelopes — you can only unseal the outermost box after every envelope inside it is opened in reverse order of how they were sealed, so the top of the stack must always match the closer you're holding.
Trace "([)]" through the optimal algorithm character by character. At which character does the check fail, and why does that one mismatch correctly prove the whole string is invalid — even though it contains exactly one (, one ), one [, and one ]?