DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Valid Parentheses | Stack

#algorithms #interview #java #leetcode
leetcode.com

Problem Statement

Given a string containing only:

(
)
[
]
{
}
Enter fullscreen mode Exit fullscreen mode

Determine whether the parentheses are valid.

A string is valid if:

  • Every opening bracket has a matching closing bracket.
  • Brackets close in the correct order.

Brute Force Intuition

In an interview, you can explain it like this:

We can repeatedly scan the string and remove valid pairs like (), {}, and []. If the string eventually becomes empty, it's valid.

However, this requires repeatedly traversing the string.

Complexity

  • Time Complexity: O(N²)
  • Space Complexity: O(N)

Brute Force Code 

class Solution {

    public boolean isValid(String s) {

        while (true) {

            String reduced = s.replace("()", "")
                              .replace("[]", "")
                              .replace("{}", "");

            if (reduced.equals(s))
                break;

            s = reduced;
        }

        return s.isEmpty();
    }
}
Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Notice something important.

Whenever we encounter:

Opening Bracket
Enter fullscreen mode Exit fullscreen mode

we don't know when it will close.

So we need to remember it.

Which data structure remembers the most recent element?

Stack
Enter fullscreen mode Exit fullscreen mode

Pattern Recognition

Whenever you see:

  • Matching Brackets
  • Nested Structures
  • Reverse Order Processing

Think:

Stack

Key Observation

For every character:

Opening Bracket 

Push into Stack
Enter fullscreen mode Exit fullscreen mode

Closing Bracket 

Top should contain
its matching opening bracket.
Enter fullscreen mode Exit fullscreen mode

If:

  • Stack is empty
  • Top doesn't match

Return:

false
Enter fullscreen mode Exit fullscreen mode

Optimal Java Solution 

class Solution {

    public boolean isValid(String s) {

        Stack<Character> st = new Stack<>();

        for (char c : s.toCharArray()) {

            if (c == '(' || c == '[' || c == '{') {

                st.push(c);

            } else if (c == ')') {

                if (st.isEmpty() || st.peek() != '(')
                    return false;

                st.pop();

            } else if (c == ']') {

                if (st.isEmpty() || st.peek() != '[')
                    return false;

                st.pop();

            } else {

                if (st.isEmpty() || st.peek() != '{')
                    return false;

                st.pop();
            }
        }

        return st.isEmpty();
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input 

s = "{[()]}"
Enter fullscreen mode Exit fullscreen mode

Step 1 

{

Push
Enter fullscreen mode Exit fullscreen mode

Stack:

{
Enter fullscreen mode Exit fullscreen mode

Step 2 

[

Push
Enter fullscreen mode Exit fullscreen mode

Stack:

[
{
Enter fullscreen mode Exit fullscreen mode

Step 3 

(

Push
Enter fullscreen mode Exit fullscreen mode

Stack:

(
[
{
Enter fullscreen mode Exit fullscreen mode

Step 4 

)

Top = (

Match ✓

Pop
Enter fullscreen mode Exit fullscreen mode

Stack:

[
{
Enter fullscreen mode Exit fullscreen mode

Step 5 

]

Top = [

Match ✓

Pop
Enter fullscreen mode Exit fullscreen mode

Stack:

{
Enter fullscreen mode Exit fullscreen mode

Step 6 

}

Top = {

Match ✓

Pop
Enter fullscreen mode Exit fullscreen mode

Stack:

Empty
Enter fullscreen mode Exit fullscreen mode

Answer:

true
Enter fullscreen mode Exit fullscreen mode

Why Stack Works?

The most recently opened bracket must be closed first.

Example:

{ [ ( ) ] }
Enter fullscreen mode Exit fullscreen mode

The closing order is exactly the reverse of the opening order.

This is the LIFO (Last In, First Out) property of a Stack.

Complexity Analysis

Metric Complexity
Time Complexity O(N)
Space Complexity O(N)

Interview One-Liner

Push every opening bracket onto the stack. For each closing bracket, ensure it matches the stack's top. If every bracket matches and the stack is empty at the end, the string is valid.

Pattern Learned 

Matching Symbols
+
Nested Structure
+
Reverse Closing Order

=> Stack
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Valid Parentheses
  • Remove Outermost Parentheses
  • Minimum Remove to Make Valid Parentheses
  • Longest Valid Parentheses
  • Decode String

Memory Trick

Think:

Opening Bracket
        ↓
Push
Enter fullscreen mode Exit fullscreen mode 
Closing Bracket
        ↓
Matches Top ?
Enter fullscreen mode Exit fullscreen mode 
Yes → Pop

No → Invalid
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Open

↓

Remember

↓

Close

↓

Match

↓

Remove
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Validate brackets" or "Matching parentheses"

your brain should immediately think:

Stack (LIFO) 🚀

Top comments (0)