LeetMotion

Valid ParenthesesEasy

Intuition Approaches Solution Visualizer

Valid Parentheses

Easy📚 Stack / Monotonic StackStringStack

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Pattern Recognition & Intuition

Why this is a Stack / Monotonic Stack problem

📚

Stack / Monotonic Stack

Maintain a sorted structure to answer "next greater/smaller" in O(n).

A monotonic stack maintains elements in strictly increasing or decreasing order as you push. When a new element violates the order, you pop until the order is restored. This gives O(n) solutions to problems that would naively require O(n²) comparisons — like "next greater element", "largest rectangle in histogram", "daily temperatures".

MENTAL MODEL

Push an element. Before pushing, pop everything that your new element "beats" (is greater than for increasing stack, less than for decreasing). Those popped elements have found their answer.

INTUITION

For "next greater element": scan left-to-right. Maintain a stack of elements waiting for their "next greater". When you encounter a new element X, it is the "next greater" for all stack elements smaller than X — so pop them and record X as their answer. Push X itself and wait.

SIGNALS — WHEN TO USE THIS PATTERN

"Next greater/smaller element to the right/left"
"Largest rectangle in histogram", "trapping rain water"
"Daily temperatures", "stock span problem"
"Minimum in sliding window" (monotonic deque)
Any "previous/next element that satisfies a monotonic condition"

Approaches & Trade-offs

From brute force to optimal — understand every step of the journey

BRUTE FORCE

Brute Force

⏱ O(n²)💾 O(1)

✦ OPTIMAL

Optimal

⏱ O(n) — each element is pushed and popped at most once💾 O(n) for the stack

Single pass left-to-right. Maintain a stack of indices. For each element, pop indices whose "next greater" is the current element.

ALGORITHM STEPS

Initialize an empty stack (stores indices) and result = [-1] * n
For each index i: while stack and nums[stack[-1]] < nums[i]: pop idx, result[idx] = nums[i]
Push i onto the stack
Anything remaining in the stack at the end has no next greater → stays -1

TIME

O(n) — each element is pushed and popped at most once

SPACE

O(n) for the stack

Stack stores indices, not values — needed when you want positions, not just values.

def next_greater(nums):
    n = len(nums)
    result, stack = [-1] * n, []
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]   # nums[i] is next greater!
        stack.append(i)
    return result

Key Insight & Common Pitfalls

THE "AHA" MOMENT

Each element is pushed once and popped once — O(n) total operations despite the while loop inside the for loop. The key realization: when you push element X onto an increasing stack, you've already ensured everything below X in the stack is greater than X. So X is "waiting" for something greater. This amortized O(1) per element is the core efficiency.

COMMON MISTAKES

✕Pushing values instead of indices — you often need the index to fill result[idx]
✕Wrong monotonicity direction: "next greater" needs a decreasing stack (pop when curr > top)
✕Forgetting elements left in the stack have no answer (they stay -1)
✕"Largest rectangle": need to process remaining stack elements after the loop ends

PRO TIPS

›For "previous greater": scan right-to-left, same logic reversed
›Circular array problems: duplicate the array (or use % n) and run two passes
›"Trapping Rain Water": for each cell, min(max_left, max_right) - height. Use two passes or monotonic stack.
›Monotonic deque: extends to sliding window minimum/maximum (deque instead of stack)

Interactive Visualizer

Building 📚 Stack / Monotonic Stack Visualization

Generating visualization…