One of the most common stack problems you’ll encounter in coding interviews is LeetCode #20: Valid Parentheses. At first glance, it looks straightforward, but it’s an excellent exercise for understanding how stacks work and why they’re useful for matching nested structures.

Problem Statement

Given a string s containing only the characters:(){}[]

Determine whether the string is valid.

A string is considered valid if:

  1. Every opening bracket is closed by the same type of closing bracket.
  2. Brackets are closed in the correct order.
  3. Every closing bracket has a corresponding opening bracket.

Examples

Input: "[]"
Output: true
Input: "([{}])"
Output: true
Input: "[(])"
Output: false

In the last example, although every opening bracket has a matching closing bracket, they are closed in the wrong order.

The Key Observation

Whenever we encounter an opening bracket, we don’t immediately know when it will be closed.

For example:

([{}])

As we read from left to right:

  • ( opens
  • [ opens
  • { opens

Now, when we encounter }, it should match the most recently opened bracket, which is {.

This Last-In, First-Out (LIFO) behavior is exactly what a stack provides.

Why a Stack?

Think of a stack like a pile of plates.

  • You place new plates on top.
  • You always remove the top plate first.

Brackets work the same way.

Input: ([{}])

Stack progression:

(
([

([{

([

(

(empty)

Every closing bracket must match the bracket currently at the top of the stack.

My Approach

The idea is simple:

  • Keep a stack of opening brackets.
  • Maintain a mapping from closing brackets to their corresponding opening brackets.
  • If the current character is an opening bracket, push it onto the stack.
  • Otherwise:
    • If the stack is empty, the string is invalid.
    • Pop the top element.
    • If it doesn’t match the expected opening bracket, return False.
  • At the end, the stack should be empty.

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {
            ")": "(",
            "}": "{",
            "]": "["
        }

        stack = []

        for c in s:
            if c in mapping.values():
                stack.append(c)
            elif not stack or stack.pop() != mapping[c]:
                return False

        return not stack

Dry Run

Let’s walk through the input:

s = "([{}])"

Character

Action

Stack

(

Push

(

[

Push

( [

{

Push

( [ {

}

Pop { ✓

( [

]

Pop [ ✓

(

)

Pop ( ✓

Empty

The stack is empty at the end, so the string is valid.

Now consider:

s = "[(])"

Character

Action

Stack

[

Push

[

(

Push

[ (

]

Expected [ but got ( ❌

Invalid

Since the top of the stack doesn’t match the expected opening bracket, we immediately return False.

Why 

return not stack

?

After processing every character, there might still be unmatched opening brackets.

Example:

"((("

The loop finishes without finding any mismatches, but the stack still contains:

[(, (, (]

These brackets were never closed.

That’s why the final line is:

return not stack

This returns:

  • True if the stack is empty.
  • False if there are unmatched opening brackets remaining.

Complexity Analysis

Time Complexity

O(n)

We iterate through the string once, and every bracket is pushed and popped at most one time.

Space Complexity

O(n)

In the worst case (all opening brackets), the stack stores every character.

Key Takeaways

  • This is a classic stack problem.
  • Nested structures naturally map to a Last-In, First-Out (LIFO) data structure.
  • Using a mapping from closing brackets to opening brackets keeps the logic concise.
  • Returning early on the first mismatch makes the solution efficient and easy to understand.

This problem is a great introduction to stack-based algorithms and serves as a foundation for many more advanced parsing and expression evaluation problems you’ll encounter in coding interviews.