Valid Parentheses

🎯

Valid Parentheses

easySTACKAmazonGoogleFacebook

Imagine you are building a code editor that needs to instantly check if the parentheses typed by a user are balanced and correctly nested.

💡 This problem is a classic example of using a stack to match pairs. Beginners often struggle because they try to check pairs without a data structure that remembers the order, leading to confusion about nesting and order.

📋

Problem Statement

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. Return true if the string is valid, and false otherwise.

1 ≤ s.length ≤ 10^5s consists only of the characters '(', ')', '{', '}', '[' and ']'

💡

Example

Input"\"()[]{}\""

Outputtrue

Each opening bracket is matched correctly and in order.

Input"\"(]\""

Outputfalse

The closing bracket ']' does not match the last opening bracket '('.

• Empty string → true
• Single opening bracket '(' → false
• Single closing bracket ')' → false
• String with only one type of bracket but unbalanced, e.g. '(((' → false

⚠️

Common Mistakes

Not checking if stack is empty before popping

Runtime error or incorrect false positives

✅ Always check if stack is empty before popping

Matching brackets by type but ignoring order

Incorrectly accepts strings like '([)]'

✅ Use stack to enforce correct nesting order

Not handling empty string as valid

Returns false incorrectly

✅ Return true if input string is empty

Using string replace in brute force without careful loop control

Infinite loop or missed pairs

✅ Track string length changes and stop when no pairs removed

🧠

Brute Force (Check all possible pairs by scanning repeatedly)

💡 This approach exists to understand the problem from first principles by trying to remove valid pairs iteratively, which helps grasp the matching concept before using stacks.

Intuition

Repeatedly scan the string and remove any adjacent matching pairs of parentheses until no more can be removed. If the string becomes empty, it was valid.

Algorithm

1. Initialize a variable to track if any pairs were removed in the last pass.
2. While pairs are being removed:
3. Scan the string from left to right, removing any adjacent matching pairs '()', '{}', or '[]'.
4. If after a pass no pairs were removed, stop.
5. If the string is empty, return true; otherwise, false.

💡 This algorithm is hard to see as efficient because it repeatedly scans and modifies the string, which is costly and not scalable.

</>

Code

def isValid(s: str) -> bool:
    pairs = ['()', '{}', '[]']
    prev_length = -1
    while prev_length != len(s):
        prev_length = len(s)
        for p in pairs:
            s = s.replace(p, '')
    return len(s) == 0

# Driver code
if __name__ == '__main__':
    test_cases = ["()[]{}", "(]", "", "((", ")"]
    for tc in test_cases:
        print(f"Input: {tc} -> Output: {isValid(tc)}")

Line Notes

pairs = ['()', '{}', '[]']Defines all valid pairs to look for in the string

while prev_length != len(s):Loop continues until no pairs are removed in a pass

s = s.replace(p, '')Removes all occurrences of a valid pair in the current string

return len(s) == 0If string is empty, all pairs matched; otherwise invalid

import java.util.*;
public class ValidParentheses {
    public static boolean isValid(String s) {
        String[] pairs = {"()", "{}", "[]"};
        int prevLength = -1;
        while (prevLength != s.length()) {
            prevLength = s.length();
            for (String p : pairs) {
                s = s.replace(p, "");
            }
        }
        return s.length() == 0;
    }
    public static void main(String[] args) {
        String[] testCases = {"()[]{}", "(]", "", "((", ")"};
        for (String tc : testCases) {
            System.out.println("Input: " + tc + " -> Output: " + isValid(tc));
        }
    }
}

Line Notes

String[] pairs = {"()", "{}", "[]"};Defines all valid pairs to remove

while (prevLength != s.length())Loop until no pairs removed in last iteration

s = s.replace(p, "");Removes all occurrences of a valid pair from string

return s.length() == 0;If string empty, all pairs matched correctly

#include <iostream>
#include <string>
using namespace std;

bool isValid(string s) {
    string pairs[] = {"()", "{}", "[]"};
    int prevLength = -1;
    while (prevLength != (int)s.length()) {
        prevLength = s.length();
        for (auto &p : pairs) {
            size_t pos = string::npos;
            while ((pos = s.find(p)) != string::npos) {
                s.erase(pos, 2);
            }
        }
    }
    return s.empty();
}

int main() {
    string testCases[] = {"()[]{}", "(]", "", "((", ")"};
    for (auto &tc : testCases) {
        cout << "Input: " << tc << " -> Output: " << (isValid(tc) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

string pairs[] = {"()", "{}", "[]"};Defines valid pairs to remove

while (prevLength != (int)s.length())Loop until no pairs removed in last iteration

pos = s.find(p)Finds position of a valid pair in string

s.erase(pos, 2);Removes the found pair from the string

function isValid(s) {
    const pairs = ['()', '{}', '[]'];
    let prevLength = -1;
    while (prevLength !== s.length) {
        prevLength = s.length;
        for (const p of pairs) {
            s = s.split(p).join('');
        }
    }
    return s.length === 0;
}

// Test cases
const testCases = ["()[]{}", "(]", "", "((", ")"];
testCases.forEach(tc => console.log(`Input: ${tc} -> Output: ${isValid(tc)}`));

Line Notes

const pairs = ['()', '{}', '[]'];Defines all valid pairs to remove

while (prevLength !== s.length)Loop until no pairs removed in last iteration

s = s.split(p).join('');Removes all occurrences of a valid pair by splitting and joining

return s.length === 0;If string empty, all pairs matched correctly

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Each pass scans the string and removes pairs; in worst case, only one pair removed per pass, leading to O(n) passes and O(n) work each.

💡 For n=20, this means up to 400 operations, which is inefficient for large inputs.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Stack-Based Approach (Using Stack to Match Pairs)

💡 This approach uses a stack to remember opening brackets and matches them with closing brackets, which is intuitive and efficient for this problem.

Intuition

Push opening brackets onto a stack. For each closing bracket, check if it matches the top of the stack. If it does, pop the stack; otherwise, the string is invalid.

Algorithm

1. Initialize an empty stack.
2. Iterate over each character in the string.
3. If the character is an opening bracket, push it onto the stack.
4. If it is a closing bracket, check if the stack is empty or the top does not match; if so, return false.
5. If it matches, pop the stack.
6. After iteration, if the stack is empty, return true; else false.

💡 The key is understanding how the stack enforces correct nesting and order, which can be tricky at first.

</>

Code

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

# Driver code
if __name__ == '__main__':
    test_cases = ["()[]{}", "(]", "", "((", ")"]
    for tc in test_cases:
        print(f"Input: {tc} -> Output: {isValid(tc)}")

Line Notes

stack = []Initialize stack to keep track of opening brackets

mapping = {')': '(', '}': '{', ']': '['}Map closing brackets to their corresponding opening brackets

if char in mapping.values()If char is an opening bracket, push it

if not stack or stack[-1] != mapping[char]Check if top of stack matches the expected opening bracket

import java.util.*;
public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');
        for (char c : s.toCharArray()) {
            if (mapping.containsValue(c)) {
                stack.push(c);
            } else if (mapping.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != mapping.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        String[] testCases = {"()[]{}", "(]", "", "((", ")"};
        for (String tc : testCases) {
            System.out.println("Input: " + tc + " -> Output: " + isValid(tc));
        }
    }
}

Line Notes

Stack<Character> stack = new Stack<>();Stack to hold opening brackets

mapping.put(')', '(');Maps closing to opening brackets for easy matching

if (mapping.containsValue(c))If char is opening bracket, push it

if (stack.isEmpty() || stack.peek() != mapping.get(c))Check if top of stack matches expected opening bracket

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> mapping = {{')', '('}, {'}', '{'}, {']', '['}};
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty() || st.top() != mapping[c]) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string testCases[] = {"()[]{}", "(]", "", "((", ")"};
    for (auto &tc : testCases) {
        cout << "Input: " << tc << " -> Output: " << (isValid(tc) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

stack<char> st;Stack to hold opening brackets

unordered_map<char, char> mapping = {{')', '('}, {'}', '{'}, {']', '['}};Maps closing to opening brackets

if (c == '(' || c == '{' || c == '[')Push opening brackets onto stack

if (st.empty() || st.top() != mapping[c])Check if top of stack matches expected opening bracket

function isValid(s) {
    const stack = [];
    const mapping = {')': '(', '}': '{', ']': '['};
    for (const char of s) {
        if (Object.values(mapping).includes(char)) {
            stack.push(char);
        } else if (mapping[char]) {
            if (stack.length === 0 || stack[stack.length - 1] !== mapping[char]) {
                return false;
            }
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.length === 0;
}

// Test cases
const testCases = ["()[]{}", "(]", "", "((", ")"];
testCases.forEach(tc => console.log(`Input: ${tc} -> Output: ${isValid(tc)}`));

Line Notes

const stack = [];Stack to hold opening brackets

const mapping = {')': '(', '}': '{', ']': '['};Maps closing to opening brackets

if (Object.values(mapping).includes(char))Push opening brackets onto stack

if (stack.length === 0 || stack[stack.length - 1] !== mapping[char])Check if top of stack matches expected opening bracket

⏱

Complexity

TimeO(n)

SpaceO(n)

Each character is processed once; stack operations are O(1).

💡 For n=20, this means about 20 operations, very efficient.

Interview Verdict: Accepted / Optimal for interview coding

This is the standard solution expected in interviews for this problem.

🧠

Optimized Stack Approach (Using Array as Stack and Early Exit)

💡 This approach optimizes the stack implementation by using an array and exits early when invalidity is detected, improving runtime slightly.

Intuition

Use an array as a stack for better performance. As soon as a mismatch is found, return false immediately to avoid unnecessary processing.

Algorithm

1. Initialize an empty array to simulate a stack.
2. Iterate over each character in the string.
3. If it is an opening bracket, push it onto the array.
4. If it is a closing bracket, check if the last element matches; if not, return false immediately.
5. Pop the last element if matched.
6. Return true if the array is empty after processing.

💡 Early exit reduces unnecessary checks, which is important in large inputs.

</>

Code

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

# Driver code
if __name__ == '__main__':
    test_cases = ["()[]{}", "(]", "", "((", ")"]
    for tc in test_cases:
        print(f"Input: {tc} -> Output: {isValid(tc)}")

Line Notes

stack = []Use list as stack for efficient append/pop

pairs = {')': '(', ']': '[', '}': '{'}Dictionary for quick matching

if not stack or stack[-1] != pairs[char]Early exit if mismatch or empty stack

return not stackTrue if all matched and stack empty

import java.util.*;
public class ValidParentheses {
    public static boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = -1;
        Map<Character, Character> pairs = Map.of(')', '(', '}', '{', ']', '[');
        for (char c : s.toCharArray()) {
            if (pairs.containsValue(c)) {
                stack[++top] = c;
            } else if (pairs.containsKey(c)) {
                if (top == -1 || stack[top] != pairs.get(c)) {
                    return false;
                }
                top--;
            } else {
                return false;
            }
        }
        return top == -1;
    }
    public static void main(String[] args) {
        String[] testCases = {"()[]{}", "(]", "", "((", ")"};
        for (String tc : testCases) {
            System.out.println("Input: " + tc + " -> Output: " + isValid(tc));
        }
    }
}

Line Notes

char[] stack = new char[s.length()];Use array as stack for performance

int top = -1;Track top index of stack

if (top == -1 || stack[top] != pairs.get(c))Early exit on mismatch or empty stack

return top == -1;True if stack empty after processing

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

bool isValid(string s) {
    char *stack = new char[s.length()];
    int top = -1;
    unordered_map<char, char> pairs = {{')', '('}, {'}', '{'}, {']', '['}};
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            stack[++top] = c;
        } else {
            if (top == -1 || stack[top] != pairs[c]) {
                delete[] stack;
                return false;
            }
            top--;
        }
    }
    bool result = (top == -1);
    delete[] stack;
    return result;
}

int main() {
    string testCases[] = {"()[]{}", "(]", "", "((", ")"};
    for (auto &tc : testCases) {
        cout << "Input: " << tc << " -> Output: " << (isValid(tc) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

char *stack = new char[s.length()];Use dynamic array as stack for speed

int top = -1;Top index of stack

if (top == -1 || stack[top] != pairs[c])Early return on mismatch or empty stack

delete[] stack;Free allocated memory to avoid leaks

function isValid(s) {
    const stack = [];
    const pairs = {')': '(', '}': '{', ']': '['};
    for (const char of s) {
        if (Object.values(pairs).includes(char)) {
            stack.push(char);
        } else if (pairs[char]) {
            if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) {
                return false;
            }
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.length === 0;
}

// Test cases
const testCases = ["()[]{}", "(]", "", "((", ")"];
testCases.forEach(tc => console.log(`Input: ${tc} -> Output: ${isValid(tc)}`));

Line Notes

const stack = [];Array used as stack for efficient push/pop

const pairs = {')': '(', '}': '{', ']': '['};Mapping for quick bracket matching

if (stack.length === 0 || stack[stack.length - 1] !== pairs[char])Early exit on mismatch or empty stack

return stack.length === 0;True if all brackets matched and stack empty

⏱

Complexity

TimeO(n)

SpaceO(n)

Processes each character once with O(1) stack operations and early exits on mismatch.

💡 For large n, early exit can save significant time compared to always processing entire string.

Interview Verdict: Accepted / Slightly optimized stack solution

This is a practical optimization of the standard stack approach, useful in interviews to show attention to detail.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the stack-based approach (Approach 2 or 3) because it is efficient and clear. Mention brute force only to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Stack-Based Approach	O(n)	O(n)	No	N/A	Code this approach
3. Optimized Stack Approach	O(n)	O(n)	No	N/A	Code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the stack approach as the optimal solution. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of matching pairs.Step 3: Introduce the stack-based approach as an efficient solution.Step 4: Code the stack solution carefully, explaining each step.Step 5: Test with edge cases and discuss time/space complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of stacks, ability to handle edge cases, and write clean, efficient code that correctly matches parentheses.

Common Follow-ups

• What if the input contains other characters? → Ignore non-bracket characters or return false based on specification.
• How to handle very large inputs efficiently? → Use stack with early exit to minimize processing.

💡 These follow-ups test your ability to adapt the solution to real-world scenarios and optimize performance.

🔍

Pattern Recognition

When to Use

1) Problem involves matching pairs of characters. 2) Order and nesting matter. 3) Input is a string with brackets. 4) Need to verify correctness of bracket sequence.

Signature Phrases

'valid parentheses''open brackets must be closed in correct order'

NOT This Pattern When

Problems involving arithmetic evaluation or expression parsing require more than just matching pairs.

Similar Problems

Longest Valid Parentheses - extends this problem to find longest valid substringGenerate Parentheses - generates all valid combinations instead of validation

Practice

1. You are given an integer array and need to determine if there exists a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force triple nested loops checking all triplets

B. Greedy approach scanning from left to right picking local minima and maxima

C. Using a monotonic stack to track potential '3' and '2' values while iterating backwards

D. Dynamic programming with prefix minimum and suffix maximum arrays

Solution

1. Step 1: Understand the 132 pattern condition

   The problem requires finding a subsequence i < j < k with nums[i] < nums[k] < nums[j], which is the 132 pattern.

2. Step 2: Identify the approach that achieves O(n) time

   The monotonic stack approach iterates from right to left, maintaining candidates for the '3' and '2' elements efficiently, achieving linear time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is known optimal for 132 pattern detection [OK]

Hint: Monotonic stack solves 132 pattern in O(n) [OK]

Common Mistakes:

• Thinking brute force is acceptable for large inputs
• Confusing greedy with monotonic stack
• Assuming DP is needed

2. The following code attempts to evaluate Reverse Polish Notation expressions. Identify the line containing the subtle bug that causes incorrect results on some inputs.

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                left = stack.pop()
                right = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

medium

A. Line where 'right = stack.pop()' is assigned

B. Line where 'stack.append(ops[token](left, right))' is called

C. Line where 'left = stack.pop()' is assigned

D. Line where 'stack.append(int(token))' is called

Solution

1. Step 1: Understand operand order importance

   Operators are binary and order matters; left operand must be popped before right operand.

2. Step 2: Identify bug in operand popping order

   Code pops left operand first, then right operand, which reverses operand order and causes wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping pop order fixes evaluation correctness [OK]

Hint: Left operand must be popped before right operand [OK]

Common Mistakes:

• Swapping operand pop order
• Using float division instead of int
• Not handling single operand input

3. What is the time complexity of the optimal solution that uses a fixed-size frequency array and a queue to find the first unique character in a stream of length n, and why?

medium

A. O(n^2) because each character may cause scanning the entire queue repeatedly.

B. O(n) because each character is enqueued and dequeued at most once, and frequency updates are O(1).

C. O(n log n) due to sorting the queue elements to find the first unique character.

D. O(n * 26) because for each character, frequency array of size 26 is scanned.

Solution

1. Step 1: Analyze queue operations

   Each character is enqueued once when first seen and dequeued once when found duplicate, total O(n) operations.

2. Step 2: Analyze frequency updates

   Frequency array updates are O(1) per character, no scanning needed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each character processed in constant time overall [OK]

Hint: Each character enqueued/dequeued once -> O(n) time [OK]

Common Mistakes:

• Assuming scanning queue each time causes O(n^2)
• Thinking frequency array is scanned fully each iteration
• Confusing sorting or scanning with queue operations

4. If the input matrix can contain '2's representing cells that can be counted as either 0 or 1 (i.e., flexible cells), which modification to the maximalRectangle algorithm is correct to find the largest rectangle of 1s considering '2' as 1 or 0?

hard

A. Treat '2' as '1' in all rows and run the standard maximalRectangle algorithm once.

B. Use backtracking to try all combinations of '2' as '0' or '1' and find the maximal rectangle.

C. Modify the histogram update to count '2' as 0.5 height and adjust largestRectangleArea accordingly.

D. Run maximalRectangle twice: once treating '2' as '1' and once as '0', then take the max area.

Solution

1. Step 1: Understand the flexibility of '2' cells

   Each '2' can be either 0 or 1, so multiple configurations exist.

2. Step 2: Evaluate naive approaches

   Treating all '2's as 1 or 0 misses mixed configurations; running twice is insufficient.

3. Step 3: Correct approach

   Backtracking or bitmasking all combinations of '2' assignments is needed to find the true maximal rectangle.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Only exhaustive search guarantees correctness with flexible cells [OK]

Hint: Flexible cells require exploring all assignments [OK]

Common Mistakes:

• Assuming fixed assignment for '2'
• Partial runs miss mixed cases
• Fractional heights invalid for stack approach

5. Suppose the problem is modified so that digits can be removed multiple times (i.e., you can remove the same digit repeatedly if it appears multiple times), or the input string can contain non-digit characters. Which modification to the original algorithm is necessary to handle these changes correctly?

hard

A. Use a frequency map to track digit counts and remove digits greedily based on frequency

B. Switch to a brute force approach generating all subsequences since greedy no longer applies

C. Preprocess input to filter out non-digit characters and apply the same monotonic stack algorithm without changes

D. Modify the stack to allow re-insertion of digits and skip non-digit characters during iteration

Solution

1. Step 1: Analyze impact of repeated removals and non-digit chars

   Allowing multiple removals of the same digit requires the stack to handle re-insertion or multiple passes. Non-digit chars must be skipped to avoid errors.

2. Step 2: Identify necessary algorithm modification

   The stack must be adapted to allow re-insertion or multiple removals, and iteration must skip non-digit characters to maintain correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Handling input sanitization and stack flexibility is key for this variant [OK]

Hint: Stack must handle re-insertions and skip invalid chars [OK]

Common Mistakes:

• Assuming original algorithm works unchanged
• Ignoring input sanitization
• Switching to brute force unnecessarily