Check for balanced parentheses

Dec 18, 2024 • 4 mins read
Hero Image

Problem Overview

The "Valid Parentheses" problem is a classic problem featured on LeetCode, under the topic of Stack and Queue. The problem revolves around checking if a given string containing just the characters '(', ')', '{', '}', '[', and ']' is valid. An input string is considered valid if:

  1. Open brackets are closed by the same type of brackets.
  2. Open brackets are closed in the correct order.

Example:

  • Input: "()", Output: true
  • Input: "()[]{}", Output: true
  • Input: "(]", Output: false

Understanding the Problem

To solve this problem, we need to determine if every opening bracket has a corresponding and correctly ordered closing bracket. This is essentially a problem of matching parentheses, a type of problem well-suited for stack data structures due to its Last In, First Out (LIFO) nature.

The input string is valid if all parentheses are properly balanced and nested.

Key DSA Concepts and Theory

Stack

  • Definition: A stack is a linear data structure that follows a Last In, First Out (LIFO) order where the most recently added element is the first to be removed. It supports basic operations like push, pop, peek, etc.
  • Use Case in Problem: The stack can help track the opening brackets. When a closing bracket is encountered, we can check if it matches the bracket on top of the stack.

Properties of Balanced Parentheses

  • Opening Brackets: As they appear, they are stored in the stack.
  • Closing Brackets: For each closing bracket, it should match with the top element of the stack; if it does, pop the stack.
  • Balance Check: At the end of the string, the stack should be empty for the expression to be valid.

Solution Approach

We'll employ a stack to solve this problem:

  1. Initialize an empty stack.
  2. Iterate through each character in the string:
    • If it's an opening bracket ('(', '{', '['), push it onto the stack.
    • If it's a closing bracket (')', '}', ']'), check if the stack is empty:
      • If empty: return false (no matching opening).
      • Otherwise, pop from the stack and check if the popped element is the matching opening bracket.
  3. Final Check: After processing all characters, check if the stack is empty. If it is, the string is valid; otherwise, it is not.

Here's how you can implement it in C++ and Java:

C++ Code Example

#include <iostream>
#include <stack>
#include <unordered_map>

bool isValid(std::string s) {
    std::stack<char> stack;
    std::unordered_map<char, char> pairMap = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };
    
    for (char ch : s) {
        if (pairMap.find(ch) != pairMap.end()) { // Closing bracket
            if (!stack.empty() && stack.top() == pairMap[ch]) {
                stack.pop();
            } else {
                return false;
            }
        } else { // Opening bracket
            stack.push(ch);
        }
    }
    
    return stack.empty();
}

int main() {
    std::string s = "()[]{}";
    std::cout << (isValid(s) ? "true" : "false") << std::endl;
    return 0;
}

Java Code Example

import java.util.Stack;
import java.util.HashMap;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> pairMap = new HashMap<>();
        pairMap.put(')', '(');
        pairMap.put('}', '{');
        pairMap.put(']', '[');

        for (char ch : s.toCharArray()) {
            if (pairMap.containsKey(ch)) { // Closing bracket
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if (topElement != pairMap.get(ch)) {
                    return false;
                }
            } else { // Opening bracket
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "()[]{}";
        System.out.println(solution.isValid(s));
    }
}

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once.
  • Space Complexity: O(n), in the worst case when all opening brackets are stored in the stack.

Common Mistakes to Avoid

  1. Ignoring Stack Operations: Forgetting to check if the stack is empty before performing a pop operation can lead to runtime errors.
  2. Mismatch Handling: Always ensure that the popped element matches the current closing bracket.

Similar Problems on LeetCode

  1. No. 20 - Valid Parentheses
  2. No. 32 - Longest Valid Parentheses
  3. No. 856 - Score of Parentheses
  4. No. 921 - Minimum Add to Make Parentheses Valid

Additional Resources and References