Valid Parentheses

Easystackstring
Category: Stack
Companies that ask this question:
AmazonFacebookGoogleMicrosoftBloomberg
LeetCode →NeetCode →

Approach

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets
  2. Open brackets must be closed in the correct order
  3. Every close bracket has a corresponding open bracket of the same type

Example:

  • Input: s = "()[]{}"
  • Output: true

Example 2:

  • Input: s = "([)]"
  • Output: false
  • Explanation: Brackets are not closed in the correct order

Intuition

The key insight is that the most recent unmatched opening bracket must match the next closing bracket. This "last-in, first-out" behavior is exactly what a stack provides!

When we see an opening bracket, we push it onto the stack. When we see a closing bracket, we check if it matches the top of the stack (most recent opening bracket).

Pattern Recognition

This is a classic Stack problem. The stack naturally handles the nested and ordered nature of valid parentheses.

Approach

  1. Create an empty stack
  2. For each character in the string:
    • If it's an opening bracket (, {, or [: push onto stack
    • If it's a closing bracket:
      • If stack is empty: return false (no matching opening)
      • Pop from stack and check if it matches
      • If doesn't match: return false
  3. After processing all characters, stack should be empty
  4. Return true if stack is empty, false otherwise

Edge Cases

  • Empty string: Valid (no brackets to match)
  • Only opening brackets: Invalid (stack not empty at end)
  • Only closing brackets: Invalid (stack empty when trying to match)
  • Mismatched types: "([)]" is invalid

Complexity Analysis

  • Time Complexity: O(n) - Single pass through the string
  • Space Complexity: O(n) - Stack stores up to n/2 opening brackets

Solution

java
1class Solution {
2    public boolean isValid(String s) {
3        // Stack to track opening brackets
4        Stack<Character> stack = new Stack<>();
5
6        for (char c : s.toCharArray()) {
7            // Push opening brackets onto stack
8            if (c == '(' || c == '{' || c == '[') {
9                stack.push(c);
10            }
11            // For closing brackets, check if they match
12            else {
13                // Stack empty means no matching opening bracket
14                if (stack.isEmpty()) {
15                    return false;
16                }
17
18                char top = stack.pop();
19
20                // Check if brackets match
21                if (c == ')' && top != '(') return false;
22                if (c == '}' && top != '{') return false;
23                if (c == ']' && top != '[') return false;
24            }
25        }
26
27        // Stack should be empty if all brackets matched
28        return stack.isEmpty();
29    }
30}
31
Loading visualizer...