DSA 450 Notes

Problem Statement

Given a string containing only parentheses ( and ), determine if the parentheses are balanced. A string is balanced if every opening parenthesis has a corresponding closing parenthesis in the correct order.

Example:

Input: "(())"
Output: true
Input: "()()"
Output: true
Input: "(()"
Output: false
Input: ")("
Output: false

Extended Problem: Handle multiple types: (), {}, []

Approach 1: Using Stack

Intuition

Use a stack to track opening parentheses. For each closing parenthesis, check if it matches the top of the stack.

Algorithm

Traverse the string character by character
If opening parenthesis, push to stack
If closing parenthesis:
- If stack is empty, return false
- If top doesn't match, return false
- Pop the top
Return true if stack is empty at the end

java

import java.util.*;

public class Solution {
    // Simple version
    public boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }
        
        return stack.isEmpty();
    }
    
    // Extended version
    public boolean isBalancedExtended(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 (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (mapping.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != mapping.get(c)) {
                    return false;
                }
                stack.pop();
            }
        }
        
        return stack.isEmpty();
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through the string
Space Complexity: O(n) - Stack can hold all characters in worst case

Approach 2: Using Counter (Simple Parentheses Only)

Intuition

For strings with only (), we don't need a stack. Just count: +1 for (, -1 for ). If count goes negative, it's unbalanced.

java

public boolean isBalanced(String s) {
    int count = 0;
    
    for (char c : s.toCharArray()) {
        if (c == '(') {
            count++;
        } else if (c == ')') {
            count--;
            if (count < 0) {
                return false;
            }
        }
    }
    
    return count == 0;
}

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

Approach 3: Generate All Balanced Parentheses (Related Problem)

Intuition

Generate all combinations of n pairs of balanced parentheses using backtracking.

java

import java.util.*;

public class Solution {
    public List<String> generateParentheses(int n) {
        List<String> result = new ArrayList<>();
        generate(0, 0, n, "", result);
        return result;
    }
    
    private void generate(int open, int close, int n, String current, 
                          List<String> result) {
        if (current.length() == 2 * n) {
            result.add(current);
            return;
        }
        
        if (open < n) {
            generate(open + 1, close, n, current + "(", result);
        }
        if (close < open) {
            generate(open, close + 1, n, current + ")", result);
        }
    }
}

Approach 4: Longest Valid Parentheses (Related Problem)

Intuition

Find the length of the longest valid (balanced) parentheses substring.

java

public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int maxLen = 0;
    
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    
    return maxLen;
}

Approach 5: Minimum Additions to Balance

Intuition

Find the minimum number of parentheses to add to make the string balanced.

java

public int minAddToBalance(String s) {
    int openNeeded = 0;
    int closeNeeded = 0;
    
    for (char c : s.toCharArray()) {
        if (c == '(') {
            openNeeded++;
        } else {
            if (openNeeded > 0) {
                openNeeded--;
            } else {
                closeNeeded++;
            }
        }
    }
    
    return openNeeded + closeNeeded;
}

Key Takeaways

Stack is the natural data structure for parentheses matching
For single type of parentheses, a counter suffices (O(1) space)
The key insight: closing parenthesis must match the most recent unmatched opening
Common variations:
- Check if balanced
- Generate all balanced combinations
- Find longest valid substring
- Minimum additions to balance
Extended to multiple bracket types using a mapping
This pattern is fundamental for expression parsing and compiler design
Related problems: Valid Parentheses (LC 20), Generate Parentheses (LC 22), Longest Valid Parentheses (LC 32)

Balanced Parenthesis problem [Imp]

Problem Statement

Approach 1: Using Stack

Intuition

Algorithm

Complexity Analysis

Approach 2: Using Counter (Simple Parentheses Only)

Intuition

Complexity Analysis

Approach 3: Generate All Balanced Parentheses (Related Problem)

Intuition

Approach 4: Longest Valid Parentheses (Related Problem)

Intuition

Approach 5: Minimum Additions to Balance

Intuition

Key Takeaways