Valid Parentheses - Video Solutions

Problem Overview: You receive a string containing characters ()[]{}. The goal is to determine whether every opening bracket has a matching closing bracket in the correct order. A valid string must close brackets in the reverse order they were opened, which naturally suggests a LIFO structure.

Approach 1: Stack-Based Approach (O(n) time, O(n) space)

The most common solution uses a stack. Iterate through the string character by character. When you see an opening bracket ((, [, {), push it onto the stack. When a closing bracket appears, check the top of the stack. If the top contains the matching opening bracket, pop it; otherwise the string is invalid. This works because a stack preserves the most recent unmatched opening bracket, which must be closed first.

Each character is processed exactly once. Stack operations (push and pop) run in constant time. If the stack is empty at the end of the iteration, every bracket had a correct match. The total time complexity is O(n), and the worst‑case space complexity is O(n) when all characters are opening brackets. This approach directly models the nesting behavior of brackets and is the expected interview solution.

Approach 2: Two Pointer Style Scan with Stack-Like Tracking (O(n) time, O(n) space)

A variation simulates stack behavior while scanning the string and resolving pairs immediately. You still iterate once through the string, but instead of explicitly maintaining a classical stack structure, you maintain a dynamic container or pointer representing the most recent unmatched opening bracket. When a closing bracket appears, compare it with the last stored opening bracket and remove the pair if they match.

The idea mirrors stack logic but can be implemented with an array and index pointer or a mutable string builder. Every time a valid pair forms, the pointer moves backward (effectively a pop). If a mismatch occurs, the string is invalid. This technique is sometimes described as a "two pointer" or "stack-like" simulation because one pointer advances through the input while the other tracks unresolved openings.

The complexity remains O(n) time because each character is visited once. Space usage is O(n) in the worst case for storing unmatched brackets. While conceptually similar to the stack solution, this version emphasizes how the problem can be solved with minimal data structures and simple pointer movement.

The problem falls under classic string parsing and stack pattern questions. The key insight is that closing brackets must match the most recent opening bracket.

Recommended for interviews: The stack-based approach is the standard answer interviewers expect. It demonstrates that you recognize the LIFO pattern used for nested structures like parentheses, HTML tags, and expression parsing. Discussing why a stack models the constraint correctly shows stronger understanding than simply coding the solution.