Balanced Parentheses with Stacks

1. What Makes Parentheses "Balanced"?

Before diving into the solution, let's be crystal clear about the problem. We are given a string containing three types of brackets: (), {}, and []. The string is "balanced" if two conditions are met:

1. Every opening bracket has a corresponding closing bracket of the same type.
2. The brackets are correctly nested. The most recently opened bracket must be the first one to be closed.

The core rule—"the most recently opened bracket must be the first one to be closed"—should sound familiar. It perfectly describes the LIFO behavior of a stack. This is the key insight to solving the problem efficiently.

Let's watch a short video to see this logic in action.

2. The Algorithm: Using a Stack

As the video suggests, a stack is the ideal tool for this job. The algorithm is straightforward and elegant:

1. Initialize an empty stack. We'll use this to keep track of the opening brackets we've seen so far.
2. Iterate through the input string, one character at a time.
3. If the character is an opening bracket ((, {, or [): Push it onto the stack.
4. If the character is a closing bracket (), }, or ]):
   • First, check if the stack is empty. If it is, this means we've found a closing bracket with no corresponding opening bracket. The string is unbalanced, so we can stop and return false.
   • If the stack is not empty, pop the character from the top.
   • Compare the popped opening bracket with the current closing bracket. If they do not form a matching pair (e.g., ( and ] or { and )), the string is unbalanced. Return false.
5. After the loop finishes: If we've processed the entire string, we have one final check. The stack must be empty. If it's not, it means there are opening brackets that were never closed. The string is unbalanced, so return false.
6. If the stack is empty at the end, it means every bracket was perfectly matched and nested. The string is balanced, so return true.

Let's visualize this with a dry run.

To further solidify this, the following video provides a fantastic animated walkthrough.

3. Java Implementation

Now, let's translate this algorithm into Java code. Given your background, you'll appreciate how a Map can make the code for checking bracket pairs clean and easily extensible.

In the previous lesson, we discussed java.util.Stack and how it's a legacy, thread-safe class built on Vector. For single-threaded applications like this one, the modern and preferred interface for stack operations is java.util.Deque, with java.util.ArrayDeque being the standard implementation. It's faster and more conventional for interview settings.

Here is a complete and commented implementation.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
import java.util.HashMap;

public class BalancedParentheses {

    public static boolean isValid(String s) {
        // Use ArrayDeque as our stack implementation.
        Deque<Character> stack = new ArrayDeque<>();

        // Map to hold the relationships between closing and opening brackets.
        // This is cleaner than a long if/else or switch statement.
        Map<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put(')', '(');
        bracketMap.put('}', '{');
        bracketMap.put(']', '[');

        // Iterate through each character of the string.
        for (char c : s.toCharArray()) {
            // If the character is a closing bracket...
            if (bracketMap.containsKey(c)) {
                // Check if the stack is empty. If so, there's no matching opener.
                // Also, check if the top of the stack matches the expected opener.
                // We use a placeholder '#' if the stack is empty to avoid a NullPointerException
                // and ensure the comparison fails safely.
                char topElement = stack.isEmpty() ? '#' : stack.pop();

                if (topElement != bracketMap.get(c)) {
                    return false; // Mismatch
                }
            } else {
                // If it's an opening bracket, push it onto the stack.
                stack.push(c);
            }
        }

        // After the loop, if the stack is empty, all brackets were matched.
        // If not empty, there are unclosed opening brackets.
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String expr1 = "()[]{}";
        String expr2 = "([)]";
        String expr3 = "{[]}";
        String expr4 = "((())";

        System.out.println(expr1 + " is balanced: " + isValid(expr1)); // true
        System.out.println(expr2 + " is balanced: " + isValid(expr2)); // false
        System.out.println(expr3 + " is balanced: " + isValid(expr3)); // true
        System.out.println(expr4 + " is balanced: " + isValid(expr4)); // false
    }
}

For more examples and a slightly different coding style, you can review the provided articles.

Complexity Analysis

• Time Complexity: O(n)
  We iterate through the input string of length n exactly once. Each stack operation (push and pop) takes constant time, O(1).
• Space Complexity: O(n)
  In the worst-case scenario, the input string consists only of opening brackets (e.g., (((((( ). In this case, we would have to store all n characters on the stack.

Conclusion

Fantastic! You've successfully applied the stack data structure to solve a classic and practical problem. This is a big step in moving from knowing what a data structure is to understanding how and why to use it.

Key Takeaways:

• The balanced parentheses problem is a perfect use case for a stack due to its LIFO (Last-In, First-Out) nature.
• The core algorithm involves pushing opening brackets onto the stack and popping to match closing brackets.
• Three conditions can lead to an "unbalanced" result:
  1. Encountering a closing bracket when the stack is empty.
  2. Popping an opening bracket that doesn't match the current closing bracket.
  3. The stack is not empty after processing the entire string.
• The solution is highly efficient, with O(n) time and O(n) space complexity.

Preview of the next lesson:
Now that you're comfortable with this standard stack application, we'll level up. In the next lesson, we will explore a more advanced stack pattern called a monotonic stack to solve the "next greater element" problem. This pattern adds a specific ordering constraint to the elements within the stack, allowing you to solve another class of common interview questions.