Author at SyntaxFlow
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!
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.
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.
You interact with the solution to this problem every single day without realizing it. It is used in:
} in your if statement.<div> has a matching </div>.The Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Example 1:
s = "()"true( is immediately followed by its matching closing bracket ).Example 2:
s = "()[]{}"trueExample 3:
s = "(]"false( is closed by the wrong type ].Before writing any code, we must look at the constraints provided by LeetCode:
1 <= s.length <= 10^4s consists of parentheses only: '()[]{}'.Why these constraints matter:
O(N^2) time complexity algorithm might take a noticeable amount of time, pushing us to find an O(N) solution.When we analyze a valid string like ({[]}), we can make a few critical observations:
({[]}), 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.
Before we jump to the optimal solution, it is highly beneficial to understand how to solve this problem without specialized data structures.
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.
"()", "[]", or "{}"."" (effectively deleting them).Valid Input: s = "([{}])"
{}. Remove it. -> String becomes ("([])")... wait, ([]).[]. Remove it. -> String becomes ().(). Remove it. -> String becomes "".true.Invalid Input: s = "([)]"
(), [], {})."([)]"). Output: false.#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.
Now, let's look at the standard, most efficient way to solve this problem.
Instead of modifying the string, we can read it character by character from left to right.
c in the string s.c is an opening bracket ((, {, [), push it onto the stack.c is a closing bracket (), }, ]):false (we have a closing bracket with no open bracket).false.true (all brackets matched). If it is not empty, return false (some opening brackets were never closed).Dry Run
Result: Stack is empty -> Valid!
Let's visualize the stack as a physical container for the string ( { } ):
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.
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!
Here is a quick summary of how our two approaches stack up against each other:
A great engineer always checks their blind spots. Here are the edge cases your code must handle:
()[ has 3 characters. It is impossible to form pairs. Our O(1) check if (s.length() % 2 != 0) catches this immediately.(((( -> The loop finishes, but the stack isn't empty. Handled by return st.empty(); at the end.)))) -> The first character is a closing bracket, but the stack is empty. Handled by if (st.empty()) return false;.([)] -> Caught when checking if the top of the stack matches the current closing bracket.((((((((())))))))) are naturally handled up to the memory limit of the stack (well beyond the constraint of 10,000 characters).When writing this in a high-pressure interview, watch out for these pitfalls:
st.top() or st.pop() without checking if (!st.empty()), your C++ program will throw a Segmentation Fault or Undefined Behavior.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().If you are asked this in a technical interview, here is how you should conduct yourself:
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:
reference video
code link:
https://leetcode.com/problems/valid-parentheses/description/