Faangprep Logo
LoginRegister
Browse Curriculum
FAANGPrep Sprint
Easy

Valid Parentheses

Determine if the input string has valid matching brackets.
10 min read
Time: O(n)
Space: O(1)
Solve on LeetCode

Problem Understanding

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.

Example:

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

Algorithm Strategy

We use a Stack data structure.

  1. Iterate through the string char by char.
  2. If we see an open bracket ((, {, [), push it onto the stack.
  3. If we see a close bracket (), }, ]), check the top of the stack:
    • If stack is empty, it's invalid (no matching open).
    • If stack top is the matching open bracket, pop the stack.
    • Otherwise, it's a mismatch -> invalid.
  4. At the end, stack must be empty (all opened brackets were closed).

Interactive Visualization

Step 1 / 1
Empty Stack
Top Index: -1

Initializing...

1x

Watch how the stack grows with open brackets and shrinks with matching closed ones.

Dry Run

Input: ({[]})

Step Char Action Stack
1 ( Push (
2 { Push ( {
3 [ Push ( { [
4 ] Match [? Yes. Pop. ( {
5 } Match {? Yes. Pop. (
6 ) Match (? Yes. Pop. Empty
End - Stack Empty? Yes. Valid

Edge Cases & Common Mistakes

  • Empty String: Usually valid (unless constraints say otherwise).
  • Odd Length: Automatically invalid.
  • Start with Close: ]... invalid immediately.
  • Leftovers: (() stack not empty at end.

Solution

Stack implementation.

1class Solution:
2    def isValid(self, s: str) -> bool:
3        stack = []
4        mapping = {")": "(", "}": "{", "]": "["}
5        
6        for char in s:
7            if char in mapping:
8                # Closing bracket
9                top_element = stack.pop() if stack else '#'
10                if mapping[char] != top_element:
11                    return False
12            else:
13                # Opening bracket
14                stack.append(char)
15        
16        return not stack
Previous Problem
Max Sum of Distinct Subarray of Size K
Next Problem
Min Stack