Valid Parentheses Explained: Brute Force vs Stack Solution (C++) | LeetCode 20

Welcome to the ultimate guide on one of the most famous coding interview questions of all time: Valid Parentheses.

Whether you are a college student gearing up for placements, a beginner taking your first steps into Data Structures, or a seasoned LeetCode warrior brushing up on the basics, this problem is a must-know. It is the perfect gateway to understanding the Stack data structure.

In this comprehensive guide, we will break down the problem from first principles, explore a brute-force approach for educational purposes, dive deep into the optimal stack solution in C++, and cover everything an interviewer might ask you about it.

Let's dive in!

Introduction

What Are Balanced Parentheses?

In programming and mathematics, parentheses are "balanced" or "valid" when every opening bracket has a corresponding closing bracket of the same type, and they are closed in the exact reverse order of how they were opened.

Think of it like nested boxes. You cannot seal an outer box until all the smaller boxes inside it have been properly sealed.

Why is this a Common Interview Question?

Interviewers love this problem because it tests a fundamental computer science concept: Last-In, First-Out (LIFO). It is a practical, easy-to-understand problem that immediately separates candidates who understand basic data structures from those who do not.

Real-World Applications

You interact with the solution to this problem every single day without realizing it. It is used in:

• Code Editors (IDE): Highlighting unmatched brackets in VS Code or IntelliJ.
• Compiler Syntax Checking: How C++ or Java compilers know you missed a closing } in your if statement.
• Expression Evaluation: Calculators verifying mathematical formulas before computing them.
• HTML/XML Parsing: Browsers ensuring that every <div> has a matching </div>.

Problem Statement

The Problem: 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.

Examples

Example 1:

• Input: s = "()"
• Output: true
• Explanation: The opening bracket ( is immediately followed by its matching closing bracket ).

Example 2:

• Input: s = "()[]{}"
• Output: true
• Explanation: Each pair is opened and closed sequentially. All match perfectly.

Example 3:

• Input: s = "(]"
• Output: false
• Explanation: The opening bracket ( is closed by the wrong type ].

Constraints

Before writing any code, we must look at the constraints provided by LeetCode:

• 1 <= s.length <= 10^4
• s consists of parentheses only: '()[]{}'.

Why these constraints matter:

1. String Length: The string can be up to 10,000 characters long. An O(N^2) time complexity algorithm might take a noticeable amount of time, pushing us to find an O(N) solution.
2. Odd Lengths: Since every bracket needs a pair, a string with an odd length (e.g., length 3 or 999) can never be valid. We can use this to optimize our code early on.

Observations

When we analyze a valid string like ({[]}), we can make a few critical observations:

1. Pairs: Every opening bracket must have a matching closing bracket.
2. Order Matters: A closing bracket always corresponds to the most recently seen, unmatched opening bracket.
3. Inward out: In the string ({[]}), the [ is the last one opened, so it must be the first one closed by ].

Key Insight: "The latest opened must be the first closed." This screams Last-In, First-Out (LIFO). The data structure that perfectly models LIFO behavior is a Stack.

Approach 1: Brute Force (Educational)

Before we jump to the optimal solution, it is highly beneficial to understand how to solve this problem without specialized data structures.

Intuition

If a string is perfectly valid, it must contain at least one adjacent matching pair of brackets (i.e., (), [], or {}). If we repeatedly find and remove these adjacent pairs, a valid string will eventually collapse into an empty string.

Algorithm

1. Search the string for "()", "[]", or "{}".
2. If any of these pairs exist, replace them with an empty string "" (effectively deleting them).
3. Repeat steps 1 and 2 until no more valid adjacent pairs can be found.
4. If the string is completely empty at the end, it was valid. If characters remain, it was invalid.

Dry Run

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

1. String contains {}. Remove it. -> String becomes ("([])")... wait, ([]).
2. String contains []. Remove it. -> String becomes ().
3. String contains (). Remove it. -> String becomes "".
4. String is empty! Output: true.

Invalid Input: s = "([)]"

1. String contains NO adjacent valid pairs ((), [], {}).
2. Loop terminates.
3. String is not empty ("([)]"). Output: false.

C++ Implementation

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        int prevLength = -1;
        
        // Continue replacing until the string length stops changing
        while (s.length() != prevLength) {
            prevLength = s.length();
            
            size_t pos;
            while ((pos = s.find("()")) != string::npos) s.erase(pos, 2);
            while ((pos = s.find("[]")) != string::npos) s.erase(pos, 2);
            while ((pos = s.find("{}")) != string::npos) s.erase(pos, 2);
        }
        
        return s.empty();
    }
};

Complexity Analysis

Verdict: This approach is highly inefficient for long strings and is generally not accepted in interviews. However, explaining it shows the interviewer that you can think systematically.

Approach 2: Optimal Stack Solution

Now, let's look at the standard, most efficient way to solve this problem.

Intuition

Instead of modifying the string, we can read it character by character from left to right.

• If we see an opening bracket, we don't know when it will close yet, so we store it for later (push it onto a stack).
• If we see a closing bracket, it must match the last opening bracket we stored. We check the top of our stack. If it matches, great—we cross them both out (pop from the stack). If it doesn't match, or if the stack is empty, the string is invalid.

Algorithm

1. Initialize an empty stack of characters.
2. Iterate through every character c in the string s.
3. If c is an opening bracket ((, {, [), push it onto the stack.
4. If c is a closing bracket (), }, ]):
   • Check if the stack is empty. If it is, return false (we have a closing bracket with no open bracket).
   • Check the top of the stack. If it is the correct corresponding opening bracket, pop it off the stack.
   • If it is the wrong type of bracket, return false.
5. After the loop finishes, check the stack. If it is empty, return true (all brackets matched). If it is not empty, return false (some opening brackets were never closed).

Dry Run

Result: Stack is empty -> Valid!

Visual Illustration

Let's visualize the stack as a physical container for the string ( { } ):

C++ Implementation

Here is the clean, optimal, LeetCode-compatible code.

#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // Optimization: Odd length strings can never be balanced
        if (s.length() % 2 != 0) return false;
        
        stack<char> st;
        
        for (char c : s) {
            // If it's an opening bracket, push to stack
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } 
            // If it's a closing bracket
            else {
                // If stack is empty, there is no matching opening bracket
                if (st.empty()) return false;
                
                char top = st.top();
                
                // Verify if the top of the stack matches the closing bracket
                if ((c == ')' && top == '(') || 
                    (c == '}' && top == '{') || 
                    (c == ']' && top == '[')) {
                    st.pop(); // It's a match, remove the opening bracket
                } else {
                    return false; // Mismatched brackets
                }
            }
        }
        
        // If the stack is empty, all brackets were successfully matched
        return st.empty();
    }
};

Best Practice Note: You can also use a switch statement instead of the if-else chain for checking matching brackets. It compiles to slightly faster machine code via jump tables in C++, though the logic remains perfectly identical.

Complexity Analysis

Why Stack Works

To truly internalize this concept, let's step away from code for a second.

Imagine you are at a buffet, and there is a stack of clean plates. You place a blue plate down, then a red plate on top, and finally a green plate on top.

If someone wants a plate, which one do they get? They get the green one. The last plate you put down is the first one picked up.

Parentheses work exactly the same way. When you open a parenthesis (, you are putting a plate down. When you open a bracket [, you put another plate on top. To successfully resolve (close) these, you must take the top plate [ off first before you can reach the bottom plate (. The Stack data structure enforces this strict order natively!

Comparison Table

Here is a quick summary of how our two approaches stack up against each other:

Edge Cases

A great engineer always checks their blind spots. Here are the edge cases your code must handle:

• Odd Length Strings: A string like ()[ has 3 characters. It is impossible to form pairs. Our O(1) check if (s.length() % 2 != 0) catches this immediately.
• Only Opening Brackets: (((( -> The loop finishes, but the stack isn't empty. Handled by return st.empty(); at the end.
• Only Closing Brackets: )))) -> The first character is a closing bracket, but the stack is empty. Handled by if (st.empty()) return false;.
• Incorrect Order: ([)] -> Caught when checking if the top of the stack matches the current closing bracket.
• Deep Nesting: Strings like ((((((((())))))))) are naturally handled up to the memory limit of the stack (well beyond the constraint of 10,000 characters).

Common Mistakes

When writing this in a high-pressure interview, watch out for these pitfalls:

1. Popping an Empty Stack: If you see a closing bracket and immediately call st.top() or st.pop() without checking if (!st.empty()), your C++ program will throw a Segmentation Fault or Undefined Behavior.
2. Forgetting the Final Check: Just returning true at the end of the loop is a classic mistake. If the input is "[", you push it, the loop ends, and you return true. You must return st.empty().
3. Pushing Closing Brackets: Only push opening brackets. Pushing closing brackets ruins the LIFO verification process.

Interview Tips

If you are asked this in a technical interview, here is how you should conduct yourself:

• Think Out Loud: Start by saying, "Since we need to match the most recently opened bracket first, a LIFO structure like a Stack makes perfect sense."
• Acknowledge Constraints: Point out that checking for odd lengths immediately saves unnecessary processing. Interviewers love optimizations.
• Discuss Variations: An interviewer might ask, "What if there are other characters like letters in the string?" (Answer: Just ignore them and only process bracket characters).
• Extensibility: Mention how compilers use this exact concept to build Abstract Syntax Trees (ASTs). Showing broad domain knowledge gives you bonus points.

FAQs

1. Why is a stack used for this problem? A stack operates on a Last-In, First-Out (LIFO) principle. Since the most recently opened bracket must be the first one closed, the stack perfectly models this requirement.

2. Can recursion solve this? Yes! Recursion inherently uses the "call stack" in memory. However, an iterative solution with an explicit std::stack is preferred as it is easier to read and prevents Stack Overflow errors on massive inputs.

3. Why isn't a Queue suitable? A Queue uses First-In, First-Out (FIFO). If you push ( then [, a queue would expect you to close ( first. This violates the rules of nested brackets.

4. Why is the final empty stack check necessary? If the input consists of solely opening brackets (e.g., "((("), the loop will run, push everything, and terminate without errors. Returning st.empty() ensures we catch unmatched open brackets.

5. What happens if the input is empty? An empty string "" contains zero unmatched brackets, so technically it is valid. Our algorithm handles this because the for loop won't execute, and st.empty() returns true.

6. Is this actually asked in real interviews? Absolutely. It is one of the most frequently asked phone screen questions at FAANG (Meta, Amazon, Apple, Netflix, Google) and financial tech companies.

7. Can this be solved in O(1) space? No, not generally. If there are multiple types of brackets, you must remember the exact sequence of opening brackets, requiring O(N) space. (If there was only one type of bracket, say just (), you could do it in O(1) space using a simple counter integer).

8. How do code editors (like VS Code) use this? When you type in an editor, a background process runs a similar stack-based algorithm. If the stack registers an invalid state, it highlights the unmatched bracket in red.

9. What if there are other characters, like (a + b)? You can modify the code to simply continue; (skip) any character that is not one of the six bracket characters. The logic remains the same.

10. Why is this considered an "Easy" problem? It is considered easy because the optimal algorithm requires only a single pass O(N), uses a basic data structure (Stack), and the rules mapping input to output are very straightforward without complex edge cases.

video reference:

code link:

https://leetcode.com/problems/valid-parentheses/description/