Stacks & QueuesProblem 19 of 38

Expression contains redundant bracket or not

Brute Force
Time: O(n^2)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a string of balanced expression with opening and closing parentheses, check if the expression contains any redundant brackets. A bracket is redundant if:

  1. There is nothing inside it: "()"
  2. It wraps an expression that doesn't need it: "((a+b))" - outer brackets are redundant

Example:

Input: "((a+b))" Output: Yes (outer brackets are redundant) Input: "(a+(b)/c)" Output: Yes (brackets around 'b' are redundant) Input: "(a+b*(c-d))" Output: No (all brackets are necessary) Input: "((a+b)+(c+d))" Output: No (all brackets are necessary for two additions)

Approach 1: Brute Force (Nested Loop Check)

Intuition

For each pair of matching brackets, check if removing them still results in a valid expression with the same result. This is complex to implement and inefficient.

Algorithm

A simpler brute force: find matching pairs and check if there's any operator between them.

java
public class RedundantBrackets {
    public static boolean hasRedundantBracketsBruteForce(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                int count = 1;
                boolean hasOperator = false;
                
                for (int j = i + 1; j < s.length() && count > 0; j++) {
                    char c = s.charAt(j);
                    if (c == '(') count++;
                    else if (c == ')') count--;
                    else if (c == '+' || c == '-' || c == '*' || c == '/') {
                        if (count == 1) hasOperator = true;
                    }
                }
                
                if (!hasOperator) return true;
            }
        }
        
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(n^2) - for each '(' we scan until matching ')'
  • Space Complexity: O(1)

Approach 2: Using Stack (Optimal)

Intuition

Push characters onto stack until we see ')'. Then pop until we see '('. If we find an operator (+, -, *, /) between them, brackets are NOT redundant. If no operator is found, brackets ARE redundant.

Algorithm

  1. Iterate through each character
  2. If not ')': push to stack
  3. If ')':
    • Pop until '(' while tracking if any operator found
    • If no operator found, return true (redundant)
    • Pop the '(' as well
  4. If we complete iteration, return false (no redundancy)
java
import java.util.*;

public class RedundantBrackets {
    public static boolean hasRedundantBrackets(String s) {
        Stack<Character> stack = new Stack<>();
        String operators = "+-*/";
        
        for (char c : s.toCharArray()) {
            if (c == ')') {
                boolean hasOperator = false;
                
                // Pop until we find '('
                while (!stack.isEmpty() && stack.peek() != '(') {
                    char top = stack.pop();
                    if (operators.indexOf(top) != -1) {
                        hasOperator = true;
                    }
                }
                
                // Pop the '('
                if (!stack.isEmpty()) {
                    stack.pop();
                }
                
                // If no operator found between ( and ), redundant
                if (!hasOperator) {
                    return true;
                }
            } else {
                // Push everything except ')' onto stack
                stack.push(c);
            }
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        System.out.println("((a+b)): " + (hasRedundantBrackets("((a+b))") ? "Yes" : "No"));
        System.out.println("(a+(b)/c): " + (hasRedundantBrackets("(a+(b)/c)") ? "Yes" : "No"));
        System.out.println("(a+b*(c-d)): " + (hasRedundantBrackets("(a+b*(c-d))") ? "Yes" : "No"));
        System.out.println("((a+b)+(c+d)): " + (hasRedundantBrackets("((a+b)+(c+d))") ? "Yes" : "No"));
        System.out.println("(a): " + (hasRedundantBrackets("(a)") ? "Yes" : "No"));
    }
}

Complexity Analysis

  • Time Complexity: O(n) - each character is pushed and popped at most once
  • Space Complexity: O(n) - stack can hold up to n characters

Detailed Trace

For string "((a+b))":

Stack: [] c='(': push '(' Stack: ['('] c='(': push '(' Stack: ['(', '('] c='a': push 'a' Stack: ['(', '(', 'a'] c='+': push '+' Stack: ['(', '(', 'a', '+'] c='b': push 'b' Stack: ['(', '(', 'a', '+', 'b'] c=')': pop until '(' - pop 'b' (not operator) - pop '+' (IS operator!) hasOperator = true - pop 'a' (not operator) - pop '(' hasOperator = true, continue Stack: ['('] c=')': pop until '(' - (nothing to pop except '(') - pop '(' hasOperator = false! REDUNDANT! Return true

Key Takeaways

  1. Brackets are redundant if there's no operator between them
  2. Stack naturally pairs '(' with its matching ')'
  3. Only need to check operators at the immediate level - nested operators don't matter for the current pair
  4. Edge cases:
    • "(a)" - redundant (no operator)
    • "()" - redundant (empty)
    • "((a+b))" - outer brackets redundant
  5. This is a common interview question testing stack fundamentals
  6. The key insight: meaningful brackets must contain at least one operator
Previous
Length of the Longest Valid Substring
Next
Implement Stack using Queue