Valid Parentheses

Learning goal: Recognize when a bracket sequence is valid and identify the information an algorithm must preserve.

Core idea A valid sequence closes brackets in the reverse order in which they were opened. This is not merely a counting problem: the algorithm must remember the most recent unmatched opener and compare each closer with it.

Algorithm plan

• Scan the string from left to right.
• Record every opening bracket.
• For a closing bracket, compare it with the latest recorded opener.
• Reject immediately if there is no opener or the types do not match.
• Accept only when the scan ends with no unmatched openers.

Micro-example For ([{}]), the opening brackets are pushed as (, [, {. The } must close { first, then ] closes [, and finally ) closes (.

Pitfalls

• Balanced counts do not guarantee valid nesting.
• A closer may appear before any opener.
• Leftover openers make the sequence invalid.

Recap

• Validity depends on both bracket type and order.
• The required memory is the sequence of unmatched openers.
• A stack is designed for this last-opened-first-closed behavior.

Learning goal: Understand why last-in, first-out behavior matches nested brackets.

Core idea When a new opener appears inside an existing pair, it must be closed before the outer pair can close. Therefore, the newest opener is always the only legal candidate for the next closer. A stack exposes that candidate at its top in constant time.

Data structure model

Micro-example After reading ([, the stack is [(, [] conceptually, with [ on top. A ] is valid now; a ) is not, because it skips the inner pair.

Pitfalls

• Looking at the oldest opener reverses the required nesting rule.
• Popping before checking the type can hide a mismatch.
• Treating all bracket characters as interchangeable loses essential information.

Recap

• The stack top is the next opener that must be closed.
• Matching removes one completed pair.
• A mismatch proves the entire string is invalid.

Learning goal: Translate the stack idea into a precise one-pass procedure.

Core idea Use a mapping from each closer to its required opener. On an opener, push it. On a closer, the stack must be nonempty and its top must equal the mapped opener; otherwise return false immediately. After processing all characters, return whether the stack is empty.

Algorithm plan

1. Create an empty stack and a closer-to-opener map.
2. For each character ch:
   • If ch is an opener, push it.
   • Otherwise, check the stack top against its expected opener.
   • If the check fails, return false.
   • If it succeeds, pop the opener.
3. Return stack.isEmpty().

for ch in s:
    if ch is an opener:
        push ch
    else if stack is empty or top != matching opener for ch:
        return false
    else:
        pop
return stack is empty

Micro-example For ([{}]), each closer passes its top check, and each successful check pops one opener.

Pitfalls

• Check for an empty stack before reading its top.
• Return false on the first mismatch.
• Do not return true merely because the scan completed.

Recap

• One scan performs all matching.
• Each character is pushed or popped at most once.
• The final empty-stack test catches missing closers.

Learning goal: Trace every stack change on a valid input from the problem examples.

Core idea We will process ([{}]) left to right. Opening brackets create obligations, while closing brackets discharge exactly the obligation at the stack top. The stack contents therefore show the active nesting from outermost to innermost.

Data structure model

Micro-example The deepest point is after ([ {: the top is {. The first closer is }, so it must pop {; the remaining pairs then close outward.

Pitfalls

• A valid closer can still be invalid if the top has another type.
• The stack is ordered; displaying only its size hides the key evidence.
• Empty at the end means all obligations were discharged.

Recap

• ([{}]) closes in the order }, ], ).
• Each closer matches exactly one stack top.
• The final empty stack establishes validity.

Learning goal: Distinguish true stack validation from tempting but incorrect shortcuts.

Core idea Bracket counts answer only whether totals balance. They do not answer whether each closer arrives in the correct nesting position. For example, ([)] contains one matching pair of each type, but ] tries to close [ while ( is still on top, so the string is invalid.

Algorithm plan

• Reject a closer when the stack is empty.
• Reject a closer whose type differs from the top.
• Pop only after a successful match.
• At the end, reject any nonempty stack.

Micro-example For ([)], the stack after ([ is [(, []. The next character is ), but the top is [, so return false immediately.

Pitfalls

• ) at the beginning causes an empty-stack failure.
• (( leaves unmatched openers.
• A mismatch should not be repaired by searching deeper in the stack; nesting requires the top.

Recap

• Counts are necessary but not sufficient.
• The top mismatch is decisive.
• Empty input, if allowed, is valid because its stack is empty.

Learning goal: Justify the efficiency of stack-based bracket validation and summarize the reusable pattern.

Core idea The algorithm makes one left-to-right pass. Each character is examined once, and every opening bracket is pushed at most once and popped at most once. The stack can grow to the full input length when many openers appear before their closers.

Algorithm plan

• Scan: O(n) time.
• Push and pop operations: O(1) each.
• Total auxiliary stack space: O(n) worst case.
• Final answer: valid exactly when no mismatch occurred and the stack is empty.

Micro-example For (((( the stack reaches size 4, demonstrating the worst-case space usage. For ()[]{} , the stack never holds more than one opener at a time.

Pitfalls

• Calling the solution O(1) space because the bracket alphabet is fixed ignores the stack.
• Forgetting the final emptiness check accepts strings with missing closers.
• A one-pass algorithm is still incorrect if it ignores bracket types.

Recap

• Time complexity: O(n).
• Space complexity: O(n) in the worst case.
• The reusable pattern is: push openers, match and pop closers, then require an empty stack.