Solving Matching and Next-Element Problems with Stacks

A stack in Python: LIFO, not just “a list”

A stack follows last in, first out (LIFO) order. The latest item added is the first item removed.

Python’s built-in list is sufficient for interview stacks:

stack = []

stack.append("a")   # push
top = stack[-1]     # peek, without removing
item = stack.pop()  # pop

For a list used only at its end, these are constant-time operations:

Always check that a stack is non-empty before peeking or popping:

if stack:
    top = stack[-1]

A useful recognition rule is:

Consider a stack when the current item must interact with the most recent unresolved earlier item.

That can mean:

• an opening delimiter waiting for its matching closer;
• a function call waiting to return;
• a previous array element waiting to discover its next greater value;
• a previous temperature waiting to discover a warmer day.

The two stack problems in this lesson look different, but both store information that is unresolved so far.

Stack pattern 1: matching nested structures

Consider a string containing only brackets:

"{[()]}"

It is valid because:

1. Every opener has a corresponding closer.
2. Each closer has the correct type.
3. Closures occur in the right nesting order.

For example:

"([)]"

is invalid. The ( was opened before [, so the [ must close before the ( can close. A ) arriving while [ is still open violates that order.

The key invariant

Read the string from left to right. After processing any prefix:

The stack contains exactly the opening brackets that have not yet been matched. The top is the most recently opened unmatched bracket.

So:

• on an opening bracket, push it;
• on a closing bracket, it must match the stack top;
• at the end, the stack must be empty.

This is LIFO directly: the latest opening bracket creates the next obligation that must be satisfied.

A robust Python implementation

def is_valid_brackets(s: str) -> bool:
    expected_opener = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    stack: list[str] = []

    for char in s:
        if char in expected_opener:  # closing bracket
            if not stack or stack[-1] != expected_opener[char]:
                return False
            stack.pop()
        else:  # opening bracket, given the input contains only bracket symbols
            stack.append(char)

    return not stack

The dictionary is deliberately oriented from a closing bracket to the opener it expects:

")" -> "("
"]" -> "["
"}" -> "{"

When a closer arrives, the code checks two things before popping:

if not stack or stack[-1] != expected_opener[char]:
    return False

1. Empty stack: this closer has no earlier opener.
2. Top mismatch: there is an opener, but it is the wrong type.

Only after both checks pass do we remove the matched opener.

Trace a valid case

For:

s = "{[()]}"

the state evolves as follows:

An empty final stack means there are no unclosed openers.

For the invalid input:

"([)]"

the stack becomes:

['(', '[']

When ) appears, it expects (, but the top is [. Returning False immediately is correct: no future character can repair an ordering violation that has already happened.

Complexity and failure modes

For a string of length $n$:

• Time: $O(n)$, since each character is processed once.
• Auxiliary space: $O(n)$ in the worst case, such as "(((([[", where every symbol remains unmatched until the end.

Three common bugs are worth making automatic checks in your own code:

1. Popping without checking emptiness

   # Unsafe
   opener = stack.pop()
   

   This raises an error for inputs beginning with a closing bracket, such as ")".

2. Checking counts but not nesting order

   A count-based approach may see one ( and one ) in "([)]", but it cannot detect the ordering violation. Structural nesting requires a stack.

3. Returning True without checking leftovers

   "((("
   

   never produces a mismatch during scanning, but it is still invalid. The final return not stack is essential.

Stack pattern 2: next greater element

Now consider a different prompt:

For every element in an array, find the first strictly greater value to its right. Return -1 if none exists.

For:

nums = [2, 1, 2, 4, 3]

the answer is:

[4, 2, 4, -1, -1]

Why?

• The first 2 sees 4 as its first later value greater than 2.
• 1 sees the following 2.
• The second 2 sees 4.
• Neither 4 nor 3 has a later greater value.

Why brute force is too slow

A direct approach scans rightward from each position:

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[j] > nums[i]:
            answer[i] = nums[j]
            break

In a decreasing array such as:

[9, 8, 7, 6, 5]

every inner loop scans nearly to the end. That costs:

A stack avoids repeatedly reconsidering elements whose answer is not known yet.

Store unresolved indices

Scan from left to right. The stack contains indices whose next greater element has not been found.

When the current value is greater than the value at the stack top:

• the current value is the answer for that top index;
• pop the resolved index;
• continue, because one current value may resolve several earlier values.

def next_greater_values(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    pending: list[int] = []  # indices with unresolved next-greater values

    for i, value in enumerate(nums):
        while pending and nums[pending[-1]] < value:
            previous_index = pending.pop()
            answer[previous_index] = value

        pending.append(i)

    return answer

Use indices, not only raw values. This makes the solution correct when duplicate values occur and lets you write the answer at its original location.

The monotonic invariant

At every point in the scan:

pending holds unresolved indices, and their corresponding values are monotonically non-increasing from bottom to top.

For example, after reading:

[2, 1, 2]

the stack stores indices for values:

[2, 2]

The middle 1 was popped and resolved when the later 2 arrived. The earlier 2 remains because an equal value is not strictly greater.

The condition is therefore:

nums[pending[-1]] < value

not:

nums[pending[-1]] <= value

This distinction encodes the wording “next greater,” not “next greater-or-equal.”

Trace the algorithm

Trace:

nums = [2, 1, 2, 4, 3]

At the end, indices 3 and 4 remain unresolved, so their initial values of -1 remain in the answer:

[4, 2, 4, -1, -1]

The nested while does not imply quadratic runtime:

• every index is pushed once;
• every index is popped at most once;
• total stack operations are at most proportional to $2n$.

Thus the algorithm is:

• Time: $O(n)$
• Auxiliary space: $O(n)$

Why a popped element has found its next greater value

Suppose index j is popped when processing index i.

• i > j, so nums[i] is to the right of nums[j].
• The while condition proves nums[i] > nums[j].
• If there had been an earlier greater value between j and i, then j would have been popped when that earlier greater value was processed.

Therefore the first value that pops j is exactly its first greater value to the right.

This proof is more useful than memorizing the template: it explains why the stack can safely discard a resolved index forever.

The query version: Next Greater Element I

A common interview variant gives two arrays:

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]

Every element of nums1 occurs in nums2, and you must return its next greater value according to its location in nums2:

[-1, 3, -1]

First preprocess nums2 using the monotonic-stack function. Then build a lookup map.

def next_greater_for_queries(
    nums1: list[int],
    nums2: list[int],
) -> list[int]:
    if len(set(nums2)) != len(nums2):
        raise ValueError("This value-to-answer lookup requires unique nums2 values")

    next_values = next_greater_values(nums2)
    lookup = dict(zip(nums2, next_values))

    return [lookup[value] for value in nums1]

The uniqueness requirement matters. A dictionary such as:

{value: next_greater_value}

has one entry per value, not one entry per position. If nums2 contains duplicate values, different occurrences can have different answers; retain indices in that version instead.

If $n=\text{len(nums2)}$ and $m=\text{len(nums1)}$, this version costs:

The stack preprocessing is $O(n)$; answering each query from the dictionary is $O(1)$ on average.

Choosing between matching and monotonic stacks

Both patterns use append, [-1], and pop, but what the stack means is different.

Before writing code, name the stack’s meaning in one sentence. For example:

• “My stack contains unmatched opening brackets.”
• “My stack contains indices still waiting for a strictly greater value to their right.”

That sentence naturally leads to both the push rule and pop rule.

For next-element problems, also specify the comparison precisely:

A change from < to <= is not cosmetic; it changes the problem being solved.

Key takeaways

A stack is the right tool when the newest unresolved item must be handled first.

• For nested matching, push opening symbols and require every closing symbol to match the stack top.
• The matching-stack invariant is: the stack contains precisely the unmatched openers seen so far.
• For next greater element, store unresolved indices in a monotonic stack.
• In the left-to-right next-greater algorithm, pop while the current value is strictly greater than the value at the top index.
• Each item is pushed once and popped at most once, which makes both stack patterns $O(n)$ despite the possible inner while loop.
• Store indices rather than values when duplicates or positional answers matter.

Next, you will move to binary search and learn to implement it using explicit boundary invariants rather than fragile memorized loop conditions.