Using Stacks for Delimiter Validation

Welcome back! In our last session, we navigated the intricacies of linked lists and mastered the slow-and-fast-pointer technique for detecting cycles. That was a great exercise in pointer manipulation and reasoning about relative movement.

Today, we're shifting gears from pointer-based lists to another fundamental data structure: the stack. We'll explore its core principle—Last-In, First-Out (LIFO)—and see how it provides an elegant solution to a common class of problems involving nesting and matching. Your goal for this lesson is to learn how to use a stack to validate properly nested delimiters, a classic problem that appears frequently in interviews and is a cornerstone of parsing technologies.

This pattern is a fantastic tool for managing "pending" or "unclosed" states, a concept that you've likely encountered in different forms, such as managing nested UI components or handling asynchronous call chains in front-end development.

The Problem: Valid Parentheses

Let's start by defining the problem. You are given a string containing only the characters (, ), {, }, [ and ]. The task is to determine if the string is "valid".

A string is valid if it meets two conditions:

1. Matching Types: Every opening bracket must be closed by the same type of bracket. For example, ( must be closed by ).
2. Correct Order: Opening brackets must be closed in the correct order. The most recently opened bracket must be the first one to be closed.

Here are some examples:

• Valid: "()[]{}, "([{}])"
• Invalid: "(]" (mismatched types), "([)]" (incorrect order)

To begin, please read the problem description from AlgoMonster, which lays out these rules clearly.

From Intuition to Data Structure

How can we programmatically check for these properties? A simple approach might be to count the occurrences of each type of bracket, but this fails quickly. For instance, the string ")(" has a balanced count of parentheses, but it's clearly invalid. The order is what matters.

This brings us to the key insight. Consider the string "([{}])". As we scan from left to right:

• We see (. We need to remember it.
• We see [. We need to remember it. It was opened after (.
• We see {. We need to remember it. It was opened after [.
• Now, we see }. Which opening bracket should it match? It must match {, the last one we opened.
• Next is ]. It must match [, which is now the last unclosed bracket.
• Finally, ). It must match (, the only one left.

This pattern, where the last item added is the first one we need to deal with, is known as Last-In, First-Out (LIFO). This should immediately bring a specific data structure to mind: the stack.

The following video provides an excellent high-level overview, explaining why a simple count is insufficient and how the LIFO principle is the key.

The Stack-Based Algorithm

Now that we've identified the stack as our tool, let's formalize the algorithm. In JavaScript/TypeScript, a simple array can serve as a stack using its push() and pop() methods.

The algorithm works as follows:

1. Initialize an empty stack (e.g., const stack = [];).
2. Iterate through each character of the input string.
3. If the character is an opening bracket ((, [, or {), push it onto the stack. We're "remembering" it as an unclosed bracket.
4. If the character is a closing bracket (), ], or }):
   a. Check if the stack is empty. If it is, this closing bracket has no corresponding opener, so the string is invalid. Return false.
   b. If the stack is not empty, pop the top element. This element is the most recently seen opening bracket.
   c. Compare the popped opener with the current closing bracket. If they don't form a matching pair (e.g., { and )), the string is invalid. Return false.
5. After the loop finishes, check if the stack is empty. If it is, every opening bracket was successfully matched and closed. The string is valid. If the stack is not empty, it means there are unclosed opening brackets left over, so the string is invalid.

This image provides a great step-by-step visualization of the process for the string [{()}].

Implementation in TypeScript

There are a couple of elegant ways to handle the "matching" logic in step 4c. A common and efficient method is to use a Map or a simple object to store the relationships between closing and opening brackets.

The following resource walks through an implementation that uses this hash map approach. It's clean and easy to read.

Another clean implementation uses a Set of valid pairs. Let's look at the complete solution from AlgoMonster, which uses this technique.

Handling Edge Cases and Pitfalls

The logic seems straightforward, but it's easy to miss edge cases. What happens with a string of only opening brackets, like "(("? Or only closing brackets, like "))"? A robust solution must handle these correctly.

• "((": Our loop will finish, but the stack will contain [ '(', '(' ]. The final check (stack.length === 0) will correctly return false.
• "))": On the first character ), we'll try to pop from an empty stack. Our code must check for an empty stack before popping to avoid an error and correctly return false.

The following video and text discuss these common mistakes and how to guard against them.

The "Common Pitfalls" section in the AlgoMonster article also provides an excellent summary of what can go wrong.

Complexity Analysis

Finally, let's analyze the performance of our algorithm.

• Time Complexity: We iterate through the input string of length $n$ exactly once. Each operation inside the loop—pushing, popping, and checking a map/set—takes constant time, $O(1)$. Therefore, the total time complexity is $O(n)$.
• Space Complexity: In the worst-case scenario, the input string consists entirely of opening brackets (e.g., "((((...))))"). In this case, we would push all $n$ characters onto the stack. Therefore, the space complexity is $O(n)$.

Conclusion

You've now learned one of the most fundamental applications of the stack data structure. The "Valid Parentheses" problem is a perfect illustration of the LIFO principle and serves as a building block for more complex parsing and evaluation tasks.

Here are the key takeaways:

• The Pattern: Problems involving correctly ordered, nested structures often follow a Last-In, First-Out (LIFO) pattern.
• The Data Structure: The stack is the natural data structure for implementing LIFO logic. In JavaScript/TypeScript, an array's push() and pop() methods make it a convenient stack.
• The Algorithm:
  1. Push opening delimiters onto the stack.
  2. When a closing delimiter appears, pop from the stack and check for a match.
  3. Handle two key failure conditions: trying to pop from an empty stack, and a mismatch between the popped opener and the current closer.
  4. After iterating, ensure the stack is empty for the string to be valid.

In our next lesson, we will explore the stack's sibling, the queue. We will see how its First-In, First-Out (FIFO) behavior is suited for a different set of problems and learn how to implement an efficient queue using an array.