Introduction & Problem Explanation

The Valid Parentheses problem asks us to determine if an input string containing only the bracket characters '(', ')', '{', '}', '[' and ']' is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.
For example, "()[]{}" is valid, but "(]" or "([)]" are invalid. This logic is a foundational building block for code compilers, text editor bracket matching, and mathematical expression parsers.

Illustration of Valid Parentheses checking brackets using a Stack in Java
Real-World Analogy: The Nesting Gift Boxes

Imagine packing nested gift boxes. If you open a large red box, then open a smaller blue box inside it, you must place the blue box's lid on *first* before you can place the red box's lid. If you try to close the red box before closing the blue box inside, the structure breaks. In computer science, this Last-In, First-Out (LIFO) behavior is modeled by a Stack. An opening bracket is like opening a box (pushing it onto the stack), and a closing bracket is like placing a lid (popping from the stack and checking if the box type matches).

The Algorithmic Approach

1. Stack-Based Verification (O(n) Time, O(n) Space)

We traverse the characters of the string from left to right:

  • If we see an opening bracket ('(', '{', '['), we push it onto our stack.
  • If we see a closing bracket (')', '}', ']'):
    • We check if the stack is empty. If it is, it means we have a closing bracket with no corresponding opening bracket, so the string is invalid.
    • Otherwise, we pop the top element from the stack and compare it to the current closing bracket. If they are not a matching pair (e.g., '(' and ']'), the string is invalid.
After scanning the entire string, the stack must be empty (all opened boxes must be closed). If the stack still contains elements, it means some brackets were left unclosed. This runs in linear O(n) time and space.

Step-by-Step Execution Walkthrough

Let's trace the stack-based algorithm on the string s = "([{}])":

  1. Step 1 (Initialization): Initialize an empty Character stack: stack = [].
  2. Step 2 (Index 0: '('): Opening bracket. We push it onto the stack.
    • Stack state: ['(']
  3. Step 3 (Index 1: '['): Opening bracket. We push it onto the stack.
    • Stack state: ['(', '[']
  4. Step 4 (Index 2: '{'): Opening bracket. We push it onto the stack.
    • Stack state: ['(', '[', '{']
  5. Step 5 (Index 3: '}'): Closing bracket.
    • We check if stack is empty (false) and pop the top: top = '{'.
    • Since '{' and '}' match, we proceed.
    • Stack state: ['(', '[']
  6. Step 6 (Index 4: ']'): Closing bracket.
    • We pop the top: top = '['.
    • Since '[' and ']' match, we proceed.
    • Stack state: ['(']
  7. Step 7 (Index 5: ')'): Closing bracket.
    • We pop the top: top = '('.
    • Since '(' and ')' match, we proceed.
    • Stack state: []
  8. Step 8 (Final Check): The loop ends. We verify if stack.isEmpty(). It is empty, so we return true. The string is valid!

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • stack.push(c);: Stores opening brackets so we can match them with their corresponding closing elements in LIFO order.
  • if (stack.isEmpty()) return false;: Immediately catches unmatched closing brackets appearing before an opening bracket (e.g. ")(").
  • char top = stack.pop(); if (c == ')' && top != '(') return false;: Compares the popped opening element with the current closing symbol, ensuring the brackets close in the correct order.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Stack;

public class ValidParentheses {

    // Stack - O(n)
    public boolean isValid(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.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        ValidParentheses solver = new ValidParentheses();
        String paren = "()[]{}";

        System.out.println("--- Valid Parentheses Demonstration ---");
        System.out.printf("Input: %s, Is Valid: %b\n", paren, solver.isValid(paren));
    }
}

Conclusion

Solving the Valid Parentheses problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.