40% off Premium for a limited time
InterviewLegend

Matching and Nesting

Alex Chen20 min readEasy
In this lesson
  • Use a stack to match opening and closing elements
  • Understand why LIFO is perfect for nested structures
  • Apply this pattern to parentheses, tags, and any paired elements

Feed "([)]" to a checker that just counts brackets and it passes: one of each, perfectly balanced by the numbers. It's also complete garbage. The parenthesis opens, the square bracket opens inside it, then the parenthesis tries to close while the square bracket is still hanging open. Valid parentheses, bracket matching, HTML tag validation, they all share this trap. A closer has to match the most recent opener that's still waiting, and counting can't see "most recent." A stack can, which is why every problem in this family reduces to push openers, pop on closers, check the match.

The Pattern: Given a sequence of opening and closing elements (parentheses, brackets, tags), determine if they're properly matched and nested.

Example: "({[]})" is valid. "([)]" is not.

Why Counting Fails

The tempting shortcut is to count: equal opens and closes means balanced. Watch it fall apart:

"(())" → 2 opens, 2 closes → Valid

"())(" → 2 opens, 2 closes → Invalid

")(" → 1 open, 1 close → Invalid

Equal counts doesn't mean balanced!

A count throws away order, and order is the whole game. The real rule is that every closer has to match the most recent unmatched opener, which is exactly last-in-first-out, which is exactly a stack.

The Stack Insight

Nesting follows one rule: the innermost thing closes first.

In "({[]})":
- "(" opens first, but closes last
- "{" opens second, closes second-to-last
- "[" opens last, but closes first

The last opener is the first to close. Last In, First Out. That's literally a stack.

Visualizing the Algorithm

Start: Empty Stack
Process string "({[]})" from left to right.
(
{
[
]
}
)
0
1
2
3
4
5
→
Stack: []

The Algorithm

You saw the shape of it in the walkthrough. Openers get pushed onto the stack and wait there, while closers pop the top and check whether it matches. A pop that comes back wrong, or a closer with nothing under it to pop, kills the string on the spot. When you run out of characters the stack has to be empty, because a leftover opener is one that never found its closer.

The one trick worth stealing is the dictionary mapping each closer to the opener it expects. It turns the match into a single equality check instead of a tangle of if-statements per bracket type.

python
def is_valid(s):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}  # Closer → opener
    
    for char in s:
        if char in '({[':                      # It's an opener
            stack.append(char)                 # Push and wait
        else:                                  # It's a closer
            if not stack or stack[-1] != matching[char]:
                return False                   # Mismatch!
            stack.pop()                        # Successful match
    
    return len(stack) == 0  # All openers matched?

Run our opening villain "([)]" through the same machine. Equal counts, correct-looking on the surface, and it dies at character three:

1

"(" → Push

Stack: ["("]

2

"[" → Push

Stack: ["(", "["]

3

")" → Pop and check

Top is "[", but we need "(". Mismatch! Return False.

The three failure cases:
1. Closer with empty stack: Nothing to match against (e.g., ")")
2. Closer doesn't match top: Wrong type of bracket (e.g., "([)]")
3. End with non-empty stack: Unclosed openers remain (e.g., "(()")

Why This Works

The stack holds one invariant that never breaks: at any moment it contains exactly the openers still waiting for a partner, in the order they showed up. So when a closer arrives, the one it has to answer to is sitting right on top. If the top isn't its match, no opener deeper down can save it, and the string is dead.

Time: O(n), one pass, one character at a time. Space: O(n), since a string that's all openers like "(((((" piles n/2 of them onto the stack before a single closer arrives.

Variations of This Pattern

The same push-and-pop skeleton stretches to cover a whole family of problems. What changes is what you push and what you check:

Common variations:
- Single type of bracket: Simpler, can use a counter instead of stack
- Multiple bracket types: Exactly what we solved above
- HTML/XML tags: Push tag names, pop and compare on closing tags
- Minimum additions to make valid: Count unmatched openers + closers
- Remove minimum to make valid: Track indices of unmatched brackets
- Longest valid substring: Track indices, use stack for start positions

The General Template

Strip away the specifics and every matching problem wears this shape. Swap in your own definitions of opener, closer, and match:

python
def matching_pattern(s):
    stack = []
    for char in s:
        if is_opener(char):
            stack.append(char)  # or index, or (char, index)
        elif is_closer(char):
            if not stack or not matches(stack[-1], char):
                return False  # Unmatched or mismatch
            stack.pop()
    return len(stack) == 0  # All openers matched?

When the problem only cares about validity, push the character. When it wants to point back at where a bracket was, push the index instead, or push both as a tuple.

Practice

Push openers, pop and match closers. The edge cases are where people lose points: an empty string is valid, any single bracket is invalid, and a string that ends with openers still on the stack fails no matter how clean the rest looked.

Try it yourself

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Examples

Input: s = "()"

Output: True

Simple matching pair

Input: s = "()[]{}"

Output: True

Multiple pairs in sequence

Input: s = "(]"

Output: False

Mismatched types

Input: s = "([)]"

Output: False

Incorrect nesting order

Valid Parentheses

Loading...
Click "Run" to execute your code

Test Cases

Input: "()"Expected: True
Input: "()[]{}"Expected: True
Input: "(]"Expected: False
Input: "([)]"Expected: False
Input: "{[]}"Expected: True
Input: ""Expected: True
Input: "((("Expected: False

Solution

def solution(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Time: O(log n) | Space: O(1)

View Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

What's Next

That's the bedrock stack pattern: LIFO to match things in reverse of the order they arrived. The next lesson bends the stack itself, teaching it to hand back its minimum or maximum in O(1) no matter how many elements are buried inside.

The Matching Pattern

Any time things open and close and the most recent unmatched one is what a closer answers to, reach for a stack. Push openers, pop and match closers, and call it valid only when the stack empties out with every match having held.

Key Takeaways

  • Counting opens/closes isn't enough: order matters
  • The most recent opener matches the next closer → LIFO → Stack
  • Push openers, pop and compare on closers
  • Three failure cases: empty stack, mismatch, non-empty at end
  • Template extends to tags, minimum additions, longest valid, etc.
Next: Premium lesson