AlgoBreath

Valid Parentheses

The "Valid Parentheses" problem is a common algorithmic challenge that often serves to test one's understanding of the stack data structure and its Last In, First Out (LIFO) principle. Let's break down this problem and its solution using fundamental concepts.

Problem Statement

The challenge is to determine if a given string containing just the characters '(', ')', '{', '}', '[' and ']' is valid. A string is considered valid if:

  1. Balanced Parentheses: All open brackets must be closed by the corresponding type of brackets.
  2. Correct Order: Open brackets must be closed in the correct order.

Examples of Valid and Invalid Strings

  • Valid: "()[]", "({[]})", "{[()]}" - Every open bracket is closed by the same type of bracket in the correct order.
  • Invalid: "(]", "([)]", "{[" - Either the brackets are not of the same type, or they are not closed in the correct order.

Solution Using a Stack

The most efficient way to solve this problem is by using a stack, which perfectly fits the requirement of checking for the correct order and type of closing brackets. Here's how the algorithm works:

  1. Iterate Through the String: Go through each character in the string one by one.
  2. Push Open Brackets onto the Stack: When an open bracket ('(', '{', '[') is encountered, push it onto the stack.
  3. Check and Pop for Closing Brackets: Upon encountering a closing bracket (')', '}', ']'), check the top of the stack.
    • If the stack is empty or the top of the stack is not the corresponding opening bracket, the string is invalid.
    • If the top of the stack is the matching opening bracket, pop it from the stack.
  4. Final Check: After iterating through the string, if the stack is empty, it means all the brackets were properly closed and matched; hence, the string is valid. If the stack is not empty, some opening brackets were not closed, thus invalid.

Why a Stack?

  • LIFO Property: The last open bracket needs to be matched with the next closing bracket. This is exactly how a stack works.
  • Efficiency: Checking, pushing, and popping from the stack are all O(1) operations, making the algorithm efficient.

Pseudo Code

Here's a pseudo code representation of the solution:

function isValid(string s):
    Initialize an empty stack
    for each character in s:
        if character is an open bracket:
            Push it onto the stack
        else if character is a closing bracket:
            if the stack is empty or the top of the stack is not the matching open bracket:
                return false
            else:
                Pop the top of the stack
    return true if the stack is empty else false

Conclusion

The "Valid Parentheses" problem exemplifies the utility of stacks in scenarios where elements need to be processed in reverse order of their arrival. This problem is foundational in understanding not just stacks but also the concept of balancing and orderly processing in data structures and algorithms.

Next