Introduction

The Valid Parentheses problem involves checking whether brackets in a string are balanced correctly.

Given a string s containing:

 ( ) { } [ ]

the task is to determine:

  • whether opening brackets
    and closing brackets
    are properly matched

A valid string must satisfy:

  1. Every opening bracket
    must have a closing bracket
  2. Brackets must close
    in correct order

This problem helps in understanding:

  • stacks
  • balanced expressions
  • traversal techniques
  • matching logic

Example

Input:s = "()[]{}"

Output:
True

Explanation:
All brackets are balanced.

Input:
s = "(]"

Output:
False

Explanation:
Opening and closing brackets do not match.

Constraints

1 <= s.length <= 10^4s contains only:
( ) { } [ ]

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Repeatedly remove:
    • ()
    • {}
    • []
  2. Continue until:
    • no valid pair exists
  3. If string becomes empty:
    • valid parentheses

Otherwise:

  • invalid parentheses

This approach works but repeated replacement increases time complexity.

Steps

  1. Traverse string repeatedly.
  2. Remove valid bracket pairs.
  3. Continue until no changes occur.
  4. If string becomes empty:
    • return true
  5. Otherwise:
    • return false

Dry Run

Input:s = "({[]})"
Remove:
[]

String becomes:
({})

Remove:
{}

String becomes:
()

Remove:
()

String becomes:
""

Final Result:
True

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:Repeated string replacement is performed.

Space Complexity: O(n)
Explanation:
Extra string modifications are used.

Approach 2 : Optimized Solution (Stack)

Explanation

The optimized solution uses a Stack.

The idea is:

  1. Push opening brackets into stack
  2. When closing bracket appears:
    • check top of stack
  3. If brackets match:
    • pop stack
  4. Otherwise:
    • invalid expression

This is the standard stack-based solution.

Steps

  1. Create empty stack.
  2. Traverse string characters.
  3. Push opening brackets.
  4. Check matching closing brackets.
  5. Pop matching brackets.
  6. If stack becomes empty:
    • valid parentheses

Dry Run

Input:s = "({[]})"
Traverse (:
Push into stack

Stack:
(

Traverse {:
Push into stack

Stack:
( {

Traverse [:
Push into stack

Stack:
( { [
Traverse ]:
Match found
Pop [

Stack:
( {

Continue traversal...
Stack becomes empty

Final Result:
True

Optimized Code

Approach 2 : Optimized Solution (Stack)

Time Complexity:O(n) 
Explanation:
Each bracket is processed once.

Space Complexity: O(n)
Explanation:
Extra stack is used.

Edge Cases

  1. Empty string
  2. Only opening brackets
  3. Only closing brackets
  4. Incorrect nesting
  5. Multiple balanced groups

Why This Problem is Important

This problem helps in understanding:

  1. Stack data structure
  2. Balanced expression checking
  3. Matching logic
  4. Traversal techniques
  5. Nested structure handling

It is one of the most important stack interview problems.

Real-World Applications

Balanced expression concepts are used in:

  1. Compiler design
  2. Syntax validation
  3. Code editors
  4. Expression evaluation
  5. HTML/XML parsing

Common Mistakes

  1. Forgetting empty stack check
  2. Incorrect bracket matching
  3. Missing final stack validation
  4. Wrong push/pop order

Interview Tips

Interviewers often expect:

  1. Stack-based optimization
  2. Proper matching logic
  3. O(n) solution explanation

Always explain why:

  • opening brackets are pushed
  • closing brackets validate stack top

Related Questions

  1. Remove Adjacent Duplicates
  2. Min Stack
  3. Next Greater Element
  4. Evaluate Expression
  5. Daily Temperatures

Final Takeaway

The Valid Parentheses problem is a fundamental stack problem that teaches balanced expression validation and nested structure handling techniques. Understanding this problem builds a strong foundation for advanced stack and parsing interview problems.