Valid Parentheses - Solution & Explanation

Problem Overview: Given a string containing characters ()[]{}, determine if the parentheses are valid. A string is valid when every opening bracket has a matching closing bracket of the same type and the pairs are closed in the correct order.

This problem appears simple but tests your understanding of stack behavior and sequential validation in a string. The core challenge is ensuring that the most recently opened bracket is the first one that must close.

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

The standard solution uses a stack to track opening brackets as you iterate through the string. When you encounter an opening bracket ((, [, {), push it onto the stack. When you see a closing bracket, check the top of the stack to confirm it matches the corresponding opening type. If it matches, pop the stack; otherwise the string is invalid.

The key insight is that brackets must close in reverse order of opening. A stack naturally enforces this Last-In-First-Out behavior. At the end of the iteration, the stack must be empty for the string to be valid. This approach processes each character once, giving O(n) time complexity with O(n) auxiliary space in the worst case when all characters are opening brackets.

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

This variation simulates stack behavior using pointer movement and an array-like buffer instead of an explicit stack structure. As you iterate through the string, use one pointer as a "top" index where opening brackets are stored. When a closing bracket appears, compare it against the element at the top pointer and decrement the pointer if it matches.

The logic mirrors stack push and pop operations but uses pointer arithmetic instead of a dedicated stack container. This can slightly reduce overhead in lower-level languages and demonstrates how stack mechanics can be implemented directly with arrays or pointer indices. Each character is still processed once, resulting in O(n) time complexity and up to O(n) space for storing unmatched opening brackets.

Recommended for interviews: The stack-based solution is what most interviewers expect. It clearly demonstrates understanding of stack operations and bracket matching logic. A brute-force validation would quickly become complex with nested pairs, while the stack approach solves the problem cleanly in linear time. Knowing how to implement the same logic with a pointer-backed array is a useful follow-up optimization discussion.