DSA 450 Notes

Problem Statement

Given a string containing just the characters '(', ')', ', ', '[' and ']', determine if the input string has valid (balanced) parentheses.

A string is valid if:

Open brackets are closed by the same type of brackets
Open brackets are closed in the correct order
Every close bracket has a corresponding open bracket of the same type

Example:

Input: "()"       -> Output: true
Input: "()[]{}"   -> Output: true
Input: "(]"       -> Output: false
Input: "([)]"     -> Output: false
Input: "{[]}"     -> Output: true
Input: "((()))"   -> Output: true

Approach 1: Replace Pairs Iteratively (Brute Force)

Intuition

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

Algorithm

Keep replacing "()", "[]", "" with empty string
Repeat until no replacement is made
If string is empty, return true; else false

java

public class ValidParentheses {
    public static boolean isValidBruteForce(String s) {
        String prev = "";
        
        while (!s.equals(prev)) {
            prev = s;
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");
        }
        
        return s.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isValidBruteForce("()"));      // true
        System.out.println(isValidBruteForce("()[]{}"));  // true
        System.out.println(isValidBruteForce("(]"));      // false
        System.out.println(isValidBruteForce("([)]"));    // false
        System.out.println(isValidBruteForce("{[]}"));    // true
    }
}

Complexity Analysis

Time Complexity: O(n^2) - each replacement takes O(n), may need O(n) iterations
Space Complexity: O(n) - for string manipulation

Approach 2: Using Stack (Optimal)

Intuition

Use a stack to track opening brackets. When we encounter a closing bracket, check if it matches the most recent opening bracket (top of stack). If all brackets match and stack is empty at the end, the string is valid.

Algorithm

Iterate through each character in the string
If opening bracket: push to stack
If closing bracket:
- If stack is empty: return false (no matching opening)
- If top of stack matches: pop from stack
- Else: return false (mismatched brackets)
Return true if stack is empty at the end

java

import java.util.*;

public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> matching = new HashMap<>();
        matching.put(')', '(');
        matching.put(']', '[');
        matching.put('}', '{');
        
        for (char c : s.toCharArray()) {
            // If closing bracket
            if (matching.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != matching.get(c)) {
                    return false;
                }
                stack.pop();
            }
            // If opening bracket
            else {
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
    
    // Alternative without map
    public static boolean isValidAlt(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                
                char top = stack.peek();
                if ((c == ')' && top == '(') ||
                    (c == ']' && top == '[') ||
                    (c == '}' && top == '{')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isValid("()"));       // true
        System.out.println(isValid("()[]{}"));   // true
        System.out.println(isValid("(]"));       // false
        System.out.println(isValid("([)]"));     // false
        System.out.println(isValid("{[]}"));     // true
        System.out.println(isValid("((()))"));   // true
        System.out.println(isValid("("));        // false
        System.out.println(isValid(")"));        // false
    }
}

Complexity Analysis

Time Complexity: O(n) - single pass through the string
Space Complexity: O(n) - stack can contain at most n/2 opening brackets

Key Takeaways

Stack is perfect for matching nested structures - LIFO matches nested brackets
Opening brackets are pushed; closing brackets are matched with stack top
Three conditions for invalid:
- Closing bracket with empty stack
- Mismatched bracket types
- Non-empty stack at the end
Use a hashmap for cleaner bracket matching
This pattern applies to many problems: HTML tags, expression parsing, etc.
Early termination on mismatch improves average case performance

Check the expression has valid or Balanced parenthesis or not

Problem Statement

Approach 1: Replace Pairs Iteratively (Brute Force)

Intuition

Algorithm

Complexity Analysis

Approach 2: Using Stack (Optimal)

Intuition

Algorithm

Complexity Analysis

Key Takeaways