Monotonic Stack

Problem: Given daily temperatures, for each day return how many days you must wait until a warmer day. If there's none, put 0.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ temperatures.length ≤ 10⁵ · 30 ≤ temperatures[i] ≤ 100

From brute force to the pattern: Scanning forward from every day for a warmer one is O(n²). A monotonic stack answers each day the moment its warmer day arrives, and each day is pushed and popped once: O(n).

Spot it: "wait until a warmer day" = next greater element, but we want the distance, so we store indices.

Key insight: Keep a decreasing stack of day-indices that are still waiting. When a warmer day i arrives, it answers every colder day waiting_day it pops: answer[waiting_day] = i - waiting_day.

Approach:

1. Create answer = [0] * n. 0 means "no warmer day", the default for days that never get answered.
2. Walk the days left to right with an empty stack of indices.
3. While today is warmer than the day on top of the stack, pop that day waiting_day and write answer[waiting_day] = i - waiting_day.
4. Push today's index. It now waits for its own warmer day.
5. Days still on the stack at the end keep 0.

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        # answer[day] = how many days until a warmer day (0 = never gets warmer)
        answer = [0] * n
        # stack holds indices of days still waiting for a warmer day
        stack = []
        for i in range(n):
            today = temperatures[i]
            # Today is warmer than the day on top? Then that day's wait is over.
            while len(stack) > 0 and temperatures[stack[-1]] < today:
                waiting_day = stack.pop()             # day that just found a warmer day
                answer[waiting_day] = i - waiting_day # distance in days
            # Today starts waiting for its own warmer day
            stack.append(i)
        # Days left on the stack never got warmer, so they keep 0
        return answer

What the code is doing, line by line:

1. answer = [0] * n makes a list of n zeros. 0 is the right answer for any day that never sees a warmer day, so we only overwrite days that do.
2. stack holds day indices (not temperatures) because we need them to compute distances. Their temperatures go down from bottom to top.
3. For each day i, today is its temperature. stack[-1] is the index on top, so temperatures[stack[-1]] is that day's temperature.
4. The while loop keeps going as long as the stack is not empty and the top day is colder than today. Each such day has just found its first warmer day: pop it and store the gap i - waiting_day.
5. When the loop stops, the top (if any) is at least as warm as today, so today has to wait too: stack.append(i).
6. Return answer; leftover days on the stack keep their 0.

Dry run on the example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Final answer: [1, 1, 4, 2, 1, 1, 0, 0].

Edge cases to test:

• Strictly decreasing temperatures → all 0.
• Strictly increasing → all 1 except the last day.
• Equal temperatures are not warmer.

Complexity: O(n) time, O(n) space.

Problem: The array is circular: after the last element comes the first. For each element, return the next greater value when walking forward (wrapping around), or -1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁹ ≤ nums[i] ≤ 10⁹

From brute force to the pattern: For each element, scanning up to n − 1 steps around the circle is O(n²). Two laps of a monotonic stack handle the wrap-around in O(n).

Spot it: "next greater element" → decreasing stack. "Circular" → the answer for an element near the end may be near the start.

Key insight: Walk the array twice (step from 0 to 2n-1, using step % n). The second lap lets leftover elements find answers at the beginning. Only push indices during the first lap so nothing is answered twice.

Approach:

1. Fill answer with -1 and start an empty decreasing stack of indices.
2. Loop step from 0 to 2n - 1 and read current = nums[step % n]. The second lap plays the role of the wrap-around.
3. While the top's value is smaller than current, pop it and set its answer to current.
4. Push the index only during the first lap (step < n), so every index waits at most once.
5. Whatever remains (the maximum, and equal copies of it) keeps -1.

from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # -1 means "no greater value anywhere around the circle"
        answer = [-1] * n
        # decreasing stack of indices still waiting for an answer
        stack = []
        # Walk the array twice (2 * n steps) to simulate wrapping around
        for step in range(2 * n):
            index = step % n            # % n turns step n, n+1, ... back into 0, 1, ...
            current = nums[index]
            # current answers every smaller value waiting on the stack
            while len(stack) > 0 and nums[stack[-1]] < current:
                top_index = stack.pop()
                answer[top_index] = current
            # Only push during the first lap so each index waits at most once
            if step < n:
                stack.append(index)
        return answer

What the code is doing, line by line:

1. answer starts as all -1 (the answer for anything that never finds a bigger value). stack holds indices waiting for their answer; their values decrease from bottom to top.
2. step runs from 0 to 2n - 1. index = step % n is the real position: the remainder after dividing by n, so steps n, n+1, ... map back to 0, 1, .... This second lap is how the array "wraps around".
3. The while loop pops every waiting index whose value is smaller than current and records current as its answer, just like the next-greater template.
4. if step < n: indices are pushed only during the first lap. In the second lap we only answer leftover indices; pushing again would make them wait twice.
5. Indices still on the stack at the end (the maximum and its equal copies) keep -1.

Dry run on the example: nums = [1, 2, 1] (n = 3)

Final answer: [2, -1, 2].

Edge cases to test:

• All equal values → all −1.
• The maximum element → −1.
• The answer wraps around, e.g. [1, 2, 1] → [2, -1, 2].

Complexity: O(n) time (2n steps, each index pushed/popped once), O(n) space.

Problem: Given a number as a string and an integer k, delete exactly k digits so the remaining number is as small as possible. Return it without leading zeros ("0" if empty).

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ num.length ≤ 10⁵ · num consists of only digits. · num does not have any leading zeros except for the zero itself.

From brute force to the pattern: Trying every combination of k deletions is exponential; deleting the best single digit k times is O(n · k). A greedy monotonic stack removes every "peak" digit in one pass: O(n).

Spot it: "remove k characters to get the smallest result" while keeping order. A digit should be deleted when a smaller digit comes right after it. That's "pop the top while it's bigger than the newcomer": an increasing stack.

Key insight: Leftmost digits matter most. Greedily, whenever the top of the stack is larger than the incoming digit and you still have deletions left, pop it. If deletions remain at the end, the stack is non-decreasing, so drop from the tail.

Approach:

1. Scan the digits left to right, keeping a stack of digits you've decided to keep.
2. While you still have deletions (deletions_left > 0) and the top digit is bigger than the current digit, pop it and do deletions_left = deletions_left - 1. A smaller digit moving left always shrinks the number.
3. Push the current digit.
4. If deletions remain, the stack is non-decreasing, so pop that many digits off the end (the largest ones).
5. Strip leading zeros. Return "0" if nothing is left.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # how many digits we are still allowed to delete
        deletions_left = k
        # digits we keep, in non-decreasing order bottom -> top
        stack = []
        for i in range(len(num)):
            digit = num[i]
            # A bigger digit sitting right before a smaller one makes the number
            # bigger, so delete it (as long as we still have deletions left).
            while deletions_left > 0 and len(stack) > 0 and stack[-1] > digit:
                stack.pop()
                deletions_left = deletions_left - 1
            stack.append(digit)
        # Deletions left over: the stack is non-decreasing, so the biggest
        # digits are at the end. Remove them one at a time from the end.
        while deletions_left > 0:
            stack.pop()
            deletions_left = deletions_left - 1
        # Skip leading zeros: move 'start' past every "0" at the front
        start = 0
        while start < len(stack) and stack[start] == "0":
            start = start + 1
        # Build the answer string one character at a time
        result = ""
        for i in range(start, len(stack)):
            result = result + stack[i]
        # Nothing left means the number is zero
        if result == "":
            return "0"
        return result

What the code is doing, line by line:

1. deletions_left is a copy of k that we count down. stack holds the digits (as characters) we have decided to keep.
2. For each digit, the while loop pops the top digit if we still have deletions, the stack is not empty, and the top is bigger than digit. Comparing single-character strings like "4" > "3" works just like comparing the digits.
3. Push digit. The stack stays non-decreasing from bottom to top.
4. After the scan, any remaining deletions are used on the end of the stack, where the largest digits sit (e.g. "112" with k = 1 drops the final 2).
5. start walks forward past any "0" characters at the front, because a number never shows leading zeros.
6. The for loop from start to the end glues the remaining digits into result.
7. If every digit was removed (or all were zeros), result is empty, so return "0".

Dry run on the example: num = "1432219", k = 3

No deletions are left over and there are no leading zeros, so the answer is "1219".

Edge cases to test:

• k equals the length → "0".
• Leading zeros after deletion must be stripped, e.g. "10200", k = 1 → "200".
• Increasing digits: remove from the end.

Complexity: O(n) time, O(n) space.

Problem: Add up min(sub) over every contiguous subarray of arr. Return the sum modulo 10⁹+7.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 3 * 10⁴ · 1 ≤ arr[i] ≤ 3 * 10⁴

From brute force to the pattern: Enumerating all O(n²) subarrays and tracking their minima is O(n²). Counting each element's contribution with previous/next-smaller stacks is O(n).

Spot it: There are O(n²) subarrays, so enumerating them is too slow. Flip the question: for each element, in how many subarrays is it the minimum? That depends on the nearest smaller element on each side, which is a Monotonic Stack job.

Key insight: If arr[i]'s previous smaller is at L and its next smaller is at R, then any subarray that starts in (L, i] and ends in [i, R) has arr[i] as its minimum. That's (i − L) × (R − i) subarrays. Contribution = arr[i] × (i − L) × (R − i). To avoid double-counting equal values, use "strictly smaller" on one side and "smaller or equal" on the other.

Approach:

1. For each index i, find L = index of the previous strictly smaller element (−1 if none) with an increasing stack scanned left to right.
2. Find R = index of the next smaller-or-equal element (n if none) with a second stack scanned right to left. Mixing strict and non-strict counts tied subarrays exactly once.
3. arr[i] is the minimum of (i − L) × (R − i) subarrays.
4. Add arr[i] × (i − L) × (R − i) for every i and take the result mod 10⁹+7.

from typing import List

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        # left_count[i]  = how many choices for the LEFT end where arr[i] is the minimum
        # right_count[i] = how many choices for the RIGHT end where arr[i] is the minimum
        left_count = [0] * n
        right_count = [0] * n

        # Pass 1, left to right: previous STRICTLY smaller element
        stack = []
        for i in range(n):
            # Pop everything >= arr[i]; they are not "strictly smaller"
            while len(stack) > 0 and arr[stack[-1]] >= arr[i]:
                stack.pop()
            if len(stack) > 0:
                previous_smaller = stack[-1]
            else:
                previous_smaller = -1           # nothing smaller on the left
            left_count[i] = i - previous_smaller
            stack.append(i)

        # Pass 2, right to left: next smaller-OR-EQUAL element (tie-break)
        stack = []
        i = n - 1
        while i >= 0:
            # Pop everything > arr[i]; equal values stay and act as a wall
            while len(stack) > 0 and arr[stack[-1]] > arr[i]:
                stack.pop()
            if len(stack) > 0:
                next_smaller_or_equal = stack[-1]
            else:
                next_smaller_or_equal = n       # nothing smaller on the right
            right_count[i] = next_smaller_or_equal - i
            stack.append(i)
            i = i - 1                           # move one step to the left

        # Add up each element's contribution: value * (#left ends) * (#right ends)
        total = 0
        for i in range(n):
            contribution = arr[i] * left_count[i] * right_count[i]
            total = total + contribution
        return total % MOD

What the code is doing, line by line:

1. MOD is 10⁹+7, required by the problem because the sum can be huge. left_count and right_count start as lists of zeros, one slot per element.
2. Pass 1 (left to right) is the "previous smaller" template. Pop every index whose value is >= arr[i]; what survives on top is the nearest strictly smaller element on the left (or -1 if the stack is empty). left_count[i] = i - previous_smaller is how many start positions (previous_smaller, i] keep arr[i] as the minimum.
3. Pass 2 (right to left) uses i = n - 1 / while i >= 0 / i = i - 1 to walk backwards. It pops only values that are strictly greater, so an equal value stays as a wall. The survivor is the nearest smaller-or-equal element on the right (or n if none). right_count[i] is how many end positions [i, next_smaller_or_equal) are allowed.
4. Using "strictly smaller" on one side and "smaller or equal" on the other means a subarray with several equal minimums is counted for exactly one of them.
5. The final loop multiplies arr[i] × left_count[i] × right_count[i] (value × number of subarrays where it is the minimum), adds everything up, and returns the total mod 10⁹+7.

Dry run on the example: arr = [3, 1, 2, 4] (n = 4)

Final answer: 17 % (10⁹+7) = 17.

Edge cases to test:

• Equal values: use < on one side and ≤ on the other so no subarray is counted twice.
• A single element.
• Take the answer modulo 10⁹ + 7.

Complexity: O(n) time, O(n) space.

Problem: Bars of width 1 have heights heights[i]. Find the area of the largest rectangle that fits entirely inside the histogram.

Solve it on LeetCode ↗

Constraints: 1 ≤ heights.length ≤ 10⁵ · 0 ≤ heights[i] ≤ 10⁴

From brute force to the pattern: Expanding left and right from every bar is O(n²). An increasing stack finds each bar's left and right boundaries the moment they become known: O(n).

Spot it: A rectangle that uses bar i as its shortest bar can stretch left and right until it hits a shorter bar. "Nearest shorter on both sides" → an increasing stack.

Key insight: Keep indices with increasing heights. When bar i is shorter than the top, the top bar can't extend past i, so its rectangle is finished: its right wall is i and its left wall is the new top of the stack after popping. Width = i − left − 1. Append a sentinel height 0 at the end to flush everything.

Approach:

1. Append a sentinel height 0 so every bar gets popped at the end.
2. Keep a stack of indices whose heights are increasing.
3. When the current height h is ≤ the top's height, pop the top. Its rectangle can't extend past i.
4. Its left wall is the new top of the stack (or −1 if empty), so width = i − left − 1. Update best with height × width.
5. Push i and continue. best holds the answer at the end.

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # Copy the heights and add a sentinel bar of height 0 at the end.
        # The 0 is shorter than everything, so it pops (finishes) every bar.
        bars = []
        for i in range(len(heights)):
            bars.append(heights[i])
        bars.append(0)
        # stack holds indices whose heights are increasing bottom -> top
        stack = []
        best = 0
        for i in range(len(bars)):
            current_height = bars[i]
            # The top bar cannot stretch past i, so its rectangle is finished
            while len(stack) > 0 and bars[stack[-1]] >= current_height:
                top_index = stack.pop()
                height = bars[top_index]
                # Left wall = first shorter bar to the left (new top), or -1
                if len(stack) > 0:
                    left_wall = stack[-1]
                else:
                    left_wall = -1
                # The rectangle spans the bars strictly between the two walls
                width = i - left_wall - 1
                area = height * width
                if area > best:
                    best = area
            stack.append(i)
        return best

What the code is doing, line by line:

1. The first loop copies heights into bars (so we don't change the caller's list), then appends a sentinel 0. Because 0 is shorter than every real bar, reaching it pops everything left on the stack, so no bar is forgotten.
2. stack holds indices of bars with increasing heights. best is the biggest area found so far.
3. For each bar i, the while loop runs while the bar on top is at least as tall as the current one. That top bar can't extend to the right past i, so its rectangle is complete.
4. top_index = stack.pop() removes it; height is its height, which is the height of its rectangle.
5. After popping, the new top (if any) is the nearest shorter bar on the left: the left wall. If the stack is empty, the rectangle reaches the very start, so we use -1 as the wall.
6. width = i - left_wall - 1 counts the bars strictly between the two walls. area = height * width; keep it if it beats best.
7. Push i. The stack stays increasing.

Dry run on the example: heights = [2, 1, 5, 6, 2, 3] (so bars = [2, 1, 5, 6, 2, 3, 0])

Final answer: 10 (bars of height 5 and 6, using height 5 × width 2).

Edge cases to test:

• All bars equal height → height × n.
• Strictly increasing heights (the end sentinel matters).
• A single bar.

Complexity: O(n) time, O(n) space.

Problem: nums1 is a subset of nums2 (all values distinct). For each value in nums1, find the first greater value to its right in nums2, or -1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums1.length ≤ nums2.length ≤ 1000 · 0 ≤ nums1[i], nums2[i] ≤ 10⁴ · All integers in nums1 and nums2 are unique. · All the integers of nums1 also appear in nums2.

From brute force to the pattern: For each value of nums1, finding it in nums2 and scanning right is O(m · n). One monotonic-stack pass over nums2 plus a hash map gives O(m + n).

Spot it: "Next greater element" is the template word for word. The only twist is that answers are looked up by value, so store them in a dict.

Approach:

1. Scan nums2 with a decreasing stack of values.
2. When current is bigger than the top, pop the top and record next_bigger[top] = current.
3. Push current.
4. Answer each query in nums1: look it up in next_bigger, or use -1 if it was never popped.

from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # next_bigger[value] = first bigger value to its right in nums2
        next_bigger = {}
        # decreasing stack of VALUES (allowed because the values are distinct)
        stack = []
        for i in range(len(nums2)):
            current = nums2[i]
            # current is the first bigger value for every smaller value on top
            while len(stack) > 0 and stack[-1] < current:
                smaller_value = stack.pop()
                next_bigger[smaller_value] = current
            stack.append(current)
        # Answer each query; values never popped have no bigger value (-1)
        answer = []
        for i in range(len(nums1)):
            value = nums1[i]
            if value in next_bigger:
                answer.append(next_bigger[value])
            else:
                answer.append(-1)
        return answer

What the code is doing, line by line:

1. next_bigger is a dictionary that maps a value to the first bigger value after it in nums2. We key by value (not index) because the queries in nums1 are values.
2. stack holds values still waiting for a bigger value; they are decreasing from bottom to top. Storing values instead of indices is safe here only because all values are distinct.
3. For each current in nums2, the while loop pops every smaller value on top and records current as its answer. It is the first bigger value each of them has met.
4. Push current; it now waits for its own bigger value.
5. The second loop builds the answer for nums1. If a value is in next_bigger, use that; otherwise it was never popped, so nothing bigger came after it: use -1.

Dry run on the example: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Queries: 4 is not in the dictionary → -1; 1 → 3; 2 is not in the dictionary → -1. Final answer: [-1, 3, -1].

Edge cases to test:

• The value is the last element of nums2 → −1.
• No greater value exists → −1.
• nums1 equal to nums2.

Complexity: O(n + m) time, O(m) space.

Problem: Prices arrive one per day. For each new price, return its span: how many consecutive days, ending today and going backwards, had a price ≤ today's.

Solve it on LeetCode ↗

Constraints: 1 ≤ price ≤ 10⁵ · At most 10⁴ calls will be made to next.

From brute force to the pattern: Walking back day by day for each new price is O(n) per call. A monotonic stack merges smaller days into the next bigger one, so each price is popped once: amortised O(1) per call.

Spot it: "Going backwards until a bigger price" means you need the previous greater element, in a stream. A decreasing stack that remembers how many days each entry already covers answers it.

Approach:

1. Keep a stack of (price, span) pairs with strictly decreasing prices.
2. On a new price, start with span = 1 (today).
3. While the top's price is ≤ today's, pop it and add its span. Those days are all covered by today now.
4. Push (price, span) and return span.

class StockSpanner:
    def __init__(self):
        # Each entry is a pair (price, span). Prices are strictly decreasing
        # from bottom to top.
        self.stack = []

    def next(self, price: int) -> int:
        span = 1                                   # today always counts
        # Every earlier price <= today is covered by today's span.
        # Its span already counts the days IT covered, so add them all at once.
        while len(self.stack) > 0 and self.stack[-1][0] <= price:
            top_pair = self.stack.pop()
            top_span = top_pair[1]                 # index 1 = the span part
            span = span + top_span
        self.stack.append((price, span))
        return span

What the code is doing, line by line:

1. __init__ creates an empty stack. Each entry will be a pair (price, span); pair[0] is the price and pair[1] is the span.
2. next(price) starts with span = 1 because today itself always counts.
3. self.stack[-1][0] is the price of the top entry. While it is <= price, that day (and every day it already covered) is part of today's span, so we pop it and add its span to ours. We never need those days again: today is at least as high and blocks them.
4. Push (price, span) so later days can absorb today's whole run in one step, then return span.

Dry run on the example: calls next(100), next(80), next(60), next(70), next(60), next(75), next(85)

Outputs: [1, 1, 1, 2, 1, 4, 6].

Edge cases to test:

• Rising prices → spans grow 1, 2, 3, …
• Falling prices → every span is 1.
• Equal prices count as ≤ and are absorbed.

Complexity: Amortized O(1) per call (each day is pushed and popped once), O(n) space.

Problem: Return the lexicographically smallest subsequence of s that contains every distinct letter exactly once. (Same as LeetCode 316.)

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 1000 · s consists of lowercase English letters.

From brute force to the pattern: Generating subsequences of distinct letters is exponential. A greedy monotonic stack, with each letter's last index and an in-stack set, builds the answer in O(n).

Spot it: "Smallest result" built by deleting characters while keeping order is the same greedy as Remove K Digits: an increasing stack. The extra rule is that you can only drop a letter if it appears again later.

Approach:

1. Record last_index[letter], the last index of each letter.
2. Scan s. Skip letter if it's already on the stack.
3. While the top is bigger than letter and appears again later (last_index[top] > i), pop it. You'll pick it up again later, in a better spot.
4. Push letter and mark it as used. Glue the stack into a string at the end.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # last_index[letter] = last position where that letter appears.
        # Later positions overwrite earlier ones, so we end with the last one.
        last_index = {}
        for i in range(len(s)):
            letter = s[i]
            last_index[letter] = i
        stack = []          # letters of the answer, built left to right
        used = set()        # letters currently on the stack
        for i in range(len(s)):
            letter = s[i]
            if letter in used:
                continue    # each letter appears only once in the answer
            # Drop a bigger letter on top if it shows up again later
            # (we can re-add it later in a better position).
            while len(stack) > 0 and stack[-1] > letter and last_index[stack[-1]] > i:
                removed_letter = stack.pop()
                used.remove(removed_letter)
            stack.append(letter)
            used.add(letter)
        # Glue the letters together into one string
        result = ""
        for i in range(len(stack)):
            result = result + stack[i]
        return result

What the code is doing, line by line:

1. The first loop fills last_index. Each time a letter is seen, its entry is overwritten with the current position, so at the end it holds the last position of every letter.
2. stack is the answer being built; used is a set that answers "is this letter already on the stack?" instantly.
3. In the main loop, a letter that is already used is skipped with continue: the answer must contain each letter exactly once.
4. The while loop pops the top letter if three things are true: the stack is not empty, the top letter is bigger than the current one (so putting the current letter earlier makes the string smaller), and the top letter appears again later (last_index[...] > i), so it is safe to drop it now and add it back later. A popped letter is also removed from used.
5. Push the current letter and mark it as used.
6. The last loop glues the stacked letters into one string, left to right.

Dry run on the example: s = "bcabc", so last_index = {'b': 3, 'c': 4, 'a': 2}

Final answer: "abc".

Edge cases to test:

• All letters distinct → the letters in their original order.
• Letters already in increasing order.
• A letter whose last occurrence is early, so it can't be popped.

Complexity: O(n) time, O(1) extra space (at most 26 letters).

Problem: Return True if there are indices i < j < k with nums[i] < nums[k] < nums[j] (small, big, middle).

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 2 * 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Checking all triples is O(n³); fixing j and tracking the minimum to its left is O(n²). Scanning from the right with a monotonic stack keeps the largest valid "2" for every "3": O(n).

Spot it: For each candidate "3" (nums[j]), we want the largest "2" to its right that is smaller than it. That's a previous/next-greater relationship, so use a monotonic stack scanned from the right.

Approach:

1. Scan from right to left, keeping a decreasing stack and third = the best "2" seen so far (starts at −∞).
2. If the current value is less than third, it's a valid "1". Return True.
3. While the top is smaller than the current value, pop it into third. The current value is a "3" that sits to the left of the popped "2".
4. Push the current value. If the scan ends, return False.

from typing import List

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        # third = best "2" found so far (it has a bigger "3" to its left)
        third = float("-inf")
        # decreasing stack of values, filled while scanning right -> left
        stack = []
        i = len(nums) - 1
        while i >= 0:
            current = nums[i]
            # current < third means: current ("1") < third ("2") < some "3"
            if current < third:
                return True
            # current is a "3" for every smaller value on top; they become "2" candidates
            while len(stack) > 0 and stack[-1] < current:
                third = stack.pop()
            stack.append(current)
            i = i - 1                       # move one step to the left
        return False

What the code is doing, line by line:

1. third starts at minus infinity (float("-inf"), smaller than every number), meaning "no valid 2 found yet".
2. i = len(nums) - 1 and while i >= 0 walk the array from the last index down to 0. i = i - 1 at the bottom of the loop moves one step left.
3. If current < third, then current is the "1": it sits to the left of a "3" and a "2" with 1 < 2 < 3. Return True.
4. Otherwise, the while loop pops every value smaller than current. Each popped value has a bigger value (current) to its left, so it is a valid "2". Because the stack is decreasing, the last value popped is the biggest such "2", which gives the best chance of finding a "1" later.
5. Push current; it may serve as a "3" or a "2" for values further left.
6. If the scan finishes without finding a "1", return False.

Dry run on the example: nums = [3, 1, 4, 2] (scanning right to left)

Final answer: True (the pattern is 1, 4, 2).

Edge cases to test:

• Fewer than 3 elements → False.
• Strictly increasing → False.
• Duplicates, e.g. [1, 3, 3] → False.

Complexity: O(n) time, O(n) space.

Problem: Bars of width 1 have heights height[i]. How much rain water is trapped between them after it rains?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == height.length · 1 ≤ n ≤ 2 * 10⁴ · 0 ≤ height[i] ≤ 10⁵

From brute force to the pattern: For every bar, scan left and right for the tallest walls: O(n²). Precomputing left-max and right-max arrays makes it O(n) time but O(n) space. Two pointers drop the arrays: the lower running maximum decides the water, so one side can always be settled: O(1) space.

Spot it: Water collects in a "valley": a lower bar with a taller bar on each side. When a taller bar arrives, it closes the valleys of the shorter bars before it. That's "pop while the top is smaller".

Approach:

1. Keep a stack of indices with decreasing heights.
2. When height[i] is taller than the top, pop the top. That bar is the valley's bottom.
3. If the stack is now empty, there's no left wall, so stop. Otherwise the new top is the left wall.
4. Water layer = (min(left wall, current) − bottom) × (i − left − 1). Add it.
5. Push i. (A two-pointer version also works in O(1) space.)

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        # stack holds indices whose heights are decreasing bottom -> top
        stack = []
        water = 0
        for i in range(len(height)):
            current_height = height[i]
            # A taller bar closes the valley of the shorter bar on top
            while len(stack) > 0 and height[stack[-1]] < current_height:
                bottom = stack.pop()                  # the valley floor
                if len(stack) == 0:
                    break                             # no left wall: water spills out
                left_wall = stack[-1]
                # Water rises to the LOWER of the two walls
                if height[left_wall] < current_height:
                    water_level = height[left_wall]
                else:
                    water_level = current_height
                depth = water_level - height[bottom]
                width = i - left_wall - 1
                water = water + depth * width         # one horizontal layer of water
            stack.append(i)
        return water

What the code is doing, line by line:

1. stack holds indices of bars with decreasing heights (each one could be the left wall of a future pool). water is the running total.
2. For each bar i, the while loop runs as long as the bar on top of the stack is shorter than the current bar. That shorter bar is the floor of a valley whose right wall is bar i.
3. bottom = stack.pop() takes the floor off the stack. If the stack is now empty there is no left wall, so water would spill out: break.
4. Otherwise the new top is the left wall. Water can only rise to the lower of the two walls, so water_level is the smaller of height[left_wall] and current_height.
5. depth is how far that level is above the floor, and width is the number of columns strictly between the walls. depth * width is one horizontal slab of water, added to the total.
6. After the pops, push i. It may be the left wall of a later pool.

Dry run on the example: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Final answer: 6.

Edge cases to test:

• Fewer than 3 bars → 0.
• Monotonic heights (only rising or only falling) → 0.
• A deep valley between two tall walls, e.g. [5, 0, 0, 5] → 10.

Complexity: O(n) time, O(n) space.

Problem: In a binary matrix of "0"/"1", find the area of the largest rectangle containing only 1s.

Solve it on LeetCode ↗

Constraints: rows == matrix.length · cols == matrix[i].length · 1 ≤ rows, cols ≤ 200 · matrix[i][j] is '0' or '1'.

From brute force to the pattern: Checking every possible rectangle is O(r² · c²). Building histograms row by row and solving each in O(c) with a stack gives O(r · c).

Spot it: Treat each row as the floor of a histogram: bar c = how many consecutive 1s stand above (and including) this row in column c. Each row is then exactly problem 84.

Approach:

1. Keep heights[c]. For each row, set it to heights[c] + 1 if the cell is "1", otherwise 0.
2. Run the Largest Rectangle in Histogram stack algorithm on heights.
3. Track the best area over all rows.

from typing import List

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0
        column_count = len(matrix[0])
        # heights[j] = number of consecutive "1"s ending at the current row in column j
        heights = [0] * column_count
        best = 0
        for i in range(len(matrix)):
            row = matrix[i]
            # Grow or reset each column's bar for this row
            for j in range(column_count):
                if row[j] == "1":
                    heights[j] = heights[j] + 1
                else:
                    heights[j] = 0
            # Problem 84 on this row's histogram
            area = self.largest(heights)
            if area > best:
                best = area
        return best

    def largest(self, heights: List[int]) -> int:
        # Same as problem 84: copy the bars and add a sentinel 0
        bars = []
        for i in range(len(heights)):
            bars.append(heights[i])
        bars.append(0)
        stack = []          # indices, heights increasing
        best = 0
        for i in range(len(bars)):
            current_height = bars[i]
            while len(stack) > 0 and bars[stack[-1]] >= current_height:
                top_index = stack.pop()
                height = bars[top_index]
                if len(stack) > 0:
                    left_wall = stack[-1]
                else:
                    left_wall = -1
                width = i - left_wall - 1
                area = height * width
                if area > best:
                    best = area
            stack.append(i)
        return best

What the code is doing, line by line:

1. An empty matrix has no rectangle, so return 0 right away.
2. heights has one bar per column. heights[j] counts how many "1"s stand in an unbroken column ending at the current row.
3. For each row i, the inner loop updates every column j: a "1" makes the bar one taller, a "0" knocks it down to 0 (a rectangle of 1s can't pass through a 0).
4. After updating, heights is a histogram whose floor is this row. self.largest(heights) finds the biggest rectangle in it, and we keep the best area over all rows.
5. largest is exactly problem 84: copy the bars, add a sentinel 0, keep an increasing stack of indices, and every time a bar is popped compute height × (i − left_wall − 1).

Dry run on the example matrix [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]:

Final answer: 6 (the 2 × 3 block of 1s in rows 1–2, columns 2–4).

Edge cases to test:

• All zeros → 0.
• A single row or column.
• Values are the strings "0"/"1", not integers.

Complexity: O(R·C) time, O(C) space.

Problem: Return the maximum of every contiguous window of size k as it slides from left to right.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴ · 1 ≤ k ≤ nums.length

From brute force to the pattern: Taking max of every window is O(n · k). A monotonic deque keeps only candidates that could still become a maximum; each index is added and removed once, so O(n).

Spot it: Each window's max is "the biggest element that hasn't been beaten by a later, bigger one". That's a monotonic structure, but old indices also leave from the front, so use a deque.

Approach:

1. Keep a deque of indices whose values are decreasing from front to back.
2. For each new x, pop from the back while the back's value is ≤ x. Those values can never be a window max again.
3. Append i. If the front index has slid out of the window (≤ i − k), pop it from the front.
4. Once i ≥ k − 1, the front's value is the current window's maximum.

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # A deque is a list that is fast to change at BOTH ends:
        #   append(x) adds at the back, pop() removes from the back,
        #   popleft() removes from the front, window[0] reads the front.
        # It holds indices whose values are decreasing front -> back.
        window = deque()
        result = []
        for i in range(len(nums)):
            current = nums[i]
            # Values <= current can never be a window maximum again
            while len(window) > 0 and nums[window[-1]] <= current:
                window.pop()
            window.append(i)
            # The front index slid out of the window [i - k + 1, i]
            if window[0] <= i - k:
                window.popleft()
            # Once the first full window is reached, the front is the maximum
            if i >= k - 1:
                result.append(nums[window[0]])
        return result

What the code is doing, line by line:

1. window = deque() creates a double-ended queue. Unlike a plain list, removing from the front (popleft()) is instant. It stores indices, and the values at those indices go down from front to back.
2. result = [] collects one maximum per window.
3. The for loop visits every index i; current = nums[i] is the new value entering the window.
4. The while loop removes indices from the back whose values are <= current. While current is in the window, those smaller, older values can never be the maximum, and they will leave the window before current does.
5. window.append(i) puts the new index at the back. The deque is still decreasing.
6. The window covers indices i - k + 1 to i. If the front index is <= i - k, it has slid out, so popleft() removes it. At most one index leaves per step.
7. Once i >= k - 1 we have a full window, and the front of the deque holds the index of its maximum, so we append nums[window[0]].

Dry run on the example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Final answer: [3, 3, 5, 5, 6, 7].

Edge cases to test:

• k = 1 → the array itself.
• k = n → one value, the overall maximum.
• Decreasing input, so the deque grows to size k.

Complexity: O(n) time (each index enters and leaves the deque once), O(k) space.

Problem: n cars drive toward target on a one-lane road. Car i starts at position[i] with speed[i]. A faster car that catches a slower one ahead must slow down and drive with it as one fleet. How many fleets arrive at the target?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == position.length == speed.length · 1 ≤ n ≤ 10⁵ · 0 < target ≤ 10⁶ · 0 ≤ position[i] < target · All the values of position are unique. · 0 < speed[i] ≤ 10⁶

From brute force to the pattern: Simulating the cars minute by minute is slow and fiddly. Sorting by position and comparing arrival times with a stack (or a single "slowest time ahead" value) is O(n log n).

Spot it: Process cars from closest-to-target to farthest. Each car's solo arrival time is (target − pos) / speed. A car behind can only stay separate if it arrives later than the fleet ahead. That's a stack whose times strictly increase.

Approach:

1. Pair positions with speeds and sort by position, descending (nearest the target first).
2. For each car compute time = (target − pos) / speed.
3. If the stack is empty or time is greater than the top's time, this car can't catch the fleet ahead: push it as a new fleet.
4. Otherwise it catches up and merges into that fleet (don't push; the fleet keeps the slower, later time).
5. The stack's size is the number of fleets.

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # pair each car's position with its speed, nearest-to-target first
        cars = sorted(zip(position, speed), reverse=True)
        # arrival times of the fleets ahead, slowest (latest) on top
        stack = []
        for pos, spd in cars:
            time = (target - pos) / spd
            if not stack or time > stack[-1]:
                # can't catch the fleet ahead before the target: a new fleet
                stack.append(time)
            # else: it catches up and joins the fleet ahead (nothing to push)
        return len(stack)

What the code is doing, line by line:

1. sorted(zip(position, speed), reverse=True): zip pairs each position with its speed, and sorting the pairs by position, descending, puts the car nearest the target first.
2. time = (target - pos) / spd: how long this car would take on its own.
3. if not stack or time > stack[-1]: the fleet directly ahead arrives at stack[-1]. If this car needs more time, it never catches up: it leads a new fleet.
4. If time <= stack[-1], the car catches the fleet ahead at or before the target and is slowed to its pace, so it adds no fleet.
5. return len(stack): one entry per fleet.

Dry run on the example:

target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3] (LeetCode Example 1). Returns 3.

Edge cases to test:

• A single car → 1.
• Cars that reach the target at exactly the same time merge.
• A car already at the target.

Complexity: O(n log n) time for the sort, O(n) space.

Problem: Remove duplicate letters so each letter appears once, and return the lexicographically smallest such result (a subsequence of s).

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · s consists of lowercase English letters.

From brute force to the pattern: Generating every subsequence with each letter once and picking the smallest is exponential. The greedy stack makes each decision locally and safely, in one pass.

Spot it: "Lexicographically smallest subsequence" + greedy removal of bigger letters that come before smaller ones = a monotonic (increasing) stack, with a guard: never pop a letter that won't appear again.

Why not another pattern? Trying all subsequences with each letter once is exponential. Plain sorting ignores that the result must keep the original order.

Approach:

1. Record each letter's last index.
2. Scan s. Skip letters already in the stack.
3. While the top is bigger than the current letter and appears again later, pop it (it can be placed later, in a better position).
4. Push the current letter. The stack is the answer.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}  # last index of every letter
        stack = []
        in_stack = set()
        for i, c in enumerate(s):
            if c in in_stack:
                continue  # already placed in the best spot so far
            while stack and stack[-1] > c and last[stack[-1]] > i:
                in_stack.remove(stack.pop())  # a bigger letter that can come later: drop it now
            stack.append(c)
            in_stack.add(c)
        return "".join(stack)

What the code is doing, line by line:

1. last[c] tells us whether a letter can still be placed later.
2. Letters already in the stack are skipped: their current position is already optimal.
3. Popping a bigger top letter makes the result smaller, but only if that letter appears again (last[...] > i).
4. The stack stays as small as possible at every step and contains each letter once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All letters distinct → unchanged.
• "bcabc" → "abc".
• A big letter that appears only once must stay, e.g. "cbacdcbc" → "acdb".

Complexity: O(n) time (each letter is pushed and popped at most once), O(1) space for 26 letters.

Problem: Find the shortest subarray that, if sorted, makes the whole array sorted. Return its length.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁵ ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Sorting a copy and comparing with the original is O(n log n). Two linear scans with a running max and running min find the same boundaries in O(n).

Spot it: An element is out of place if something before it is bigger (or something after it is smaller). Tracking the running maximum from the left and the running minimum from the right finds both boundaries, the same "compare with what came before" idea as a monotonic stack, but with one value.

Why not another pattern? Sorting a copy and comparing is O(n log n). A monotonic stack finds the boundaries in O(n) with O(n) space; the running max/min version needs only O(1).

Approach:

1. Left to right with running_max: any nums[i] < running_max is out of place; the last such i is the right boundary.
2. Right to left with running_min: any nums[i] > running_min is out of place; the last such i (leftmost) is the left boundary.
3. If no boundary was found, the array is sorted: 0. Otherwise right − left + 1.

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        right = -1
        running_max = float("-inf")
        for i in range(n):
            if nums[i] < running_max:
                right = i  # something before it is bigger: i must be inside the subarray
            else:
                running_max = nums[i]
        left = 0
        running_min = float("inf")
        for i in range(n - 1, -1, -1):
            if nums[i] > running_min:
                left = i  # something after it is smaller: i must be inside
            else:
                running_min = nums[i]
        return right - left + 1 if right != -1 else 0

What the code is doing, line by line:

1. From the left, an element smaller than the maximum before it can't stay where it is, so the subarray must reach at least that far right.
2. From the right, an element bigger than the minimum after it must be inside the subarray too.
3. The last such positions in each scan are the tightest boundaries.
4. right == -1 means no element was out of place.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already sorted → 0.
• Reverse sorted → n.
• Duplicates at the boundary, e.g. [1, 3, 2, 2, 2] → 4.

Complexity: O(n) time, O(1) space.

Problem: A ramp is a pair i < j with nums[i] ≤ nums[j]; its width is j − i. Return the maximum width (0 if none).

Solve it on LeetCode ↗

Constraints: 2 ≤ nums.length ≤ 5 * 10⁴ · 0 ≤ nums[i] ≤ 5 * 10⁴

From brute force to the pattern: Checking every pair is O(n²). Only prefix minima can be optimal starts, and scanning ends from the right lets each start be matched and discarded once: O(n).

Spot it: The best start for any ramp is a "new minimum" from the left (a smaller value earlier always beats it). Those candidates form a decreasing stack. Then scan j from the right and pop every start that nums[j] can reach.

Why not another pattern? Checking all pairs is O(n²). Sorting indices by value and tracking the minimum index is O(n log n); the stack is O(n).

Approach:

1. Push index i when nums[i] is smaller than the value at the stack's top (a new minimum).
2. Scan j from the end: while the stack's top value ≤ nums[j], pop it and update the width j − top.
3. Popping is safe: any later (smaller) j would give a narrower ramp for that start.

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        stack = []  # indices of decreasing values: the only useful starts
        for i in range(len(nums)):
            if not stack or nums[i] < nums[stack[-1]]:
                stack.append(i)  # a new minimum: a better start than anything after it
        best = 0
        for j in range(len(nums) - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[j]:
                best = max(best, j - stack.pop())  # widest ramp for this start
        return best

What the code is doing, line by line:

1. A start i is only useful if no earlier index has a smaller or equal value; such indices form a decreasing sequence.
2. Scanning j from the right means the first j that works for a start is the widest one for that start.
3. After popping a start, no other j can beat that width, so it never needs to be checked again.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Strictly decreasing → 0.
• All equal → n − 1.
• The best ramp uses the first element.

Complexity: O(n) time, O(n) space.

Problem: Rebuild the BST whose preorder traversal is preorder (all values distinct).

Solve it on LeetCode ↗

Constraints: 1 ≤ preorder.length ≤ 100 · 1 ≤ preorder[i] ≤ 1000 · All the values of preorder are unique.

From brute force to the pattern: Inserting each value into the BST from the root is O(n log n) on average and O(n²) when skewed. The stack attaches each node in amortised O(1).

Spot it: In preorder, each new value is either the left child of the previous node (if smaller) or the right child of the last ancestor that is smaller than it. A stack of nodes along the current path, popped while smaller than the new value, finds that ancestor: a monotonic (decreasing) stack.

Why not another pattern? Inserting each value from the root is O(n²) on skewed input. Recursion with value bounds is also O(n); the stack makes the same logic iterative.

Approach:

1. Make the first value the root and push it.
2. For each next value: create a node. Pop while the top is smaller than it; the last popped node is its parent (right child).
3. If nothing was popped, it's the left child of the top.
4. Push the new node.

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        root = TreeNode(preorder[0])
        stack = [root]  # current path; values decrease from bottom to top
        for value in preorder[1:]:
            node = TreeNode(value)
            parent = None
            while stack and stack[-1].val < value:
                parent = stack.pop()  # the last smaller ancestor becomes the parent
            if parent is not None:
                parent.right = node  # bigger than parent: right child
            else:
                stack[-1].left = node  # smaller than the top: left child
            stack.append(node)
        return root

What the code is doing, line by line:

1. The stack holds the path of nodes that can still receive children, with values decreasing upward.
2. Popping all smaller nodes leaves parent as the deepest node smaller than value, so value is its right child.
3. If no node is smaller, value is smaller than the top and becomes its left child.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single value.
• Strictly increasing (right chain) or decreasing (left chain).
• Values that go deep left, then jump right.

Complexity: O(n) time, O(n) space.

Problem: The range of a subarray is max − min. Return the sum of the ranges of all subarrays.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 1000 · -10⁹ ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Extending every start to the right while tracking min and max is O(n²). Counting each element's contribution with monotonic stacks makes it O(n).

Spot it: Sum of ranges = (sum of all subarray maximums) − (sum of all subarray minimums). Each is the "Sum of Subarray Minimums" contribution trick: element i is the min (or max) of left × right subarrays, found with previous/next smaller (greater) elements on a monotonic stack.

Why not another pattern? Enumerating every subarray while tracking its min and max is O(n²), which passes for n ≤ 1000 but doesn't scale.

Approach:

1. Write a helper total(cmp) that returns the sum over subarrays of the min (or max) using contributions.
2. For each index, the stack gives how far it extends left and right as the min (strict on one side, non-strict on the other to avoid double counting).
3. Contribution of nums[i] = nums[i] × left × right.
4. Answer = total of maxima − total of minima.

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)

        def total(better):
            # sum over all subarrays of the element that is "best" (min or max)
            result = 0
            stack = []  # indices; a sentinel pass at i == n flushes the stack
            for i in range(n + 1):
                while stack and (i == n or better(nums[i], nums[stack[-1]])):
                    mid = stack.pop()
                    left = mid - (stack[-1] if stack else -1)  # choices for the left end
                    right = i - mid  # choices for the right end
                    result = result + nums[mid] * left * right
                stack.append(i)
            return result

        sum_max = total(lambda a, b: a > b)  # popped when a bigger value arrives
        sum_min = total(lambda a, b: a < b)  # popped when a smaller value arrives
        return sum_max - sum_min

What the code is doing, line by line:

1. total(better) computes Σ over subarrays of their best element, where better is > for maxima and < for minima.
2. When index mid is popped by i, i is the first element to its right that beats it; the new stack top is the previous element that beats-or-equals it.
3. So nums[mid] is the best element of every subarray starting in (stack top, mid] and ending in [mid, i): left × right subarrays.
4. The final iteration with i == n pops whatever is left.
5. Σ(max − min) splits into Σmax − Σmin.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single element → 0.
• Equal values (strict vs non-strict comparisons prevent double counting).
• Negative numbers.

Complexity: O(n) time, O(n) space.

Problem: From index i, odd-numbered jumps go to the smallest value ≥ arr[i] to the right (smallest index on ties); even-numbered jumps go to the largest value ≤ arr[i] to the right. Count the starting indices that can reach the end.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 2 * 10⁴ · 0 ≤ arr[i] < 10⁵

From brute force to the pattern: Scanning right from every index to find the jump target is O(n²). Sorting plus a monotonic stack finds all targets in O(n log n), and the success DP is O(n).

Spot it: Two steps: (1) for every index find its odd-jump and even-jump target, a "next greater element" in sorted order, done with a monotonic stack over indices sorted by value; (2) DP from the right: odd[i] = even[next_odd[i]], even[i] = odd[next_even[i]].

Why not another pattern? Finding targets by scanning right is O(n²). A balanced BST / sorted container scanned from the right is the other O(n log n) way.

Approach:

1. Sort indices by (value, index). Walking them in this order with a stack of indices, every index popped by a larger index i gets i as its odd target.
2. Sort indices by (−value, index) and do the same for even targets.
3. odd[n−1] = even[n−1] = True. From right to left: odd[i] = even[odd_next[i]], even[i] = odd[even_next[i]].
4. Count the indices with odd[i] true (the first jump is odd).

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        n = len(arr)

        def next_targets(order):
            # for indices visited in `order`, the next index (to the right) in that order
            target = [None] * n
            stack = []
            for i in order:
                while stack and stack[-1] < i:
                    target[stack.pop()] = i  # i is the first later index in this sorted order
                stack.append(i)
            return target

        odd_next = next_targets(sorted(range(n), key=lambda i: (arr[i], i)))  # smallest value >= arr[i]
        even_next = next_targets(sorted(range(n), key=lambda i: (-arr[i], i)))  # largest value <= arr[i]
        odd = [False] * n  # can reach the end starting with an odd jump
        even = [False] * n  # ... starting with an even jump
        odd[n - 1] = True
        even[n - 1] = True
        for i in range(n - 2, -1, -1):
            if odd_next[i] is not None:
                odd[i] = even[odd_next[i]]  # after an odd jump comes an even jump
            if even_next[i] is not None:
                even[i] = odd[even_next[i]]
        return sum(odd)  # every start begins with jump number 1 (odd)

What the code is doing, line by line:

1. Sorting by (value, index) lines indices up so that the odd target of i is the first index after i in that order that is also to the right of i in the array: a next-greater-index problem solved by the stack.
2. For even jumps, sort by (−value, index): the largest value ≤ arr[i], smallest index on ties.
3. odd[i] = even[odd_next[i]]: after an odd jump the next one is even, so the answer chains through the target.
4. The last index is already the end, for either parity.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single element → 1.
• Equal values (ties go to the smallest index).
• No jump possible from some index (target is None).

Complexity: O(n log n) time (the two sorts), O(n) space.

Problem: People stand in a line with distinct heights. Person i can see person j > i if everyone between them is shorter than both. Return how many people each person can see to their right.

Solve it on LeetCode ↗

Constraints: n == heights.length · 1 ≤ n ≤ 10⁵ · 1 ≤ heights[i] ≤ 10⁵ · All the values of heights are unique.

From brute force to the pattern: For every person, scanning right and stopping at the first taller person is O(n²). The stack keeps only people who can still be seen, and each person is popped once.

Spot it: Looking right until something taller blocks the view: next greater element territory. Scanning from the right with a decreasing stack, the people person i pops (shorter than them) are visible, and the first taller one left on the stack is visible too.

Why not another pattern? For each person, scanning right and tracking the tallest seen so far is O(n²).

Approach:

1. Scan from right to left, keeping a stack of heights that are visible from the left (decreasing from bottom to top).
2. For person i: pop everyone shorter; each popped person is visible from i.
3. If the stack is non-empty afterwards, the person on top (taller) is visible too: one more.
4. Push heights[i].

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        answer = [0] * n
        stack = []  # heights to the right that are still visible from the left (decreasing)
        for i in range(n - 1, -1, -1):
            seen = 0
            while stack and stack[-1] < heights[i]:
                stack.pop()  # shorter than i: visible, and hidden for anyone further left
                seen = seen + 1
            if stack:
                seen = seen + 1  # the first taller person is visible too
            answer[i] = seen
            stack.append(heights[i])
        return answer

What the code is doing, line by line:

1. Scanning from the right, the stack holds the people who could still be seen by someone further left.
2. Everyone popped is shorter than person i, so nothing between them blocks the view: all are visible.
3. Once popped, they're hidden behind person i for everyone to the left, so they never need to be considered again.
4. The remaining top is taller than i: visible, but it blocks everything behind it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The last person → 0.
• Increasing heights: each person sees exactly one.
• Decreasing heights: each person sees just the next one.

Complexity: O(n) time, O(n) space.

Problem: The ocean is to the right. Return, in increasing order, the indices of buildings strictly taller than every building to their right.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ heights.length ≤ 10⁵ · 1 ≤ heights[i] ≤ 10⁹

From brute force to the pattern: Comparing each building with everything to its right is O(n²); the running maximum is O(n).

Spot it: "Taller than everything to the right" → scan right to left with the running maximum. (Left to right, it's a monotonic decreasing stack: a new building pops every shorter-or-equal one, since they've lost their view.)

Why not another pattern? Checking each building against all buildings to its right is O(n²).

Approach:

1. Scan from the right with tallest = 0.
2. If heights[i] > tallest, record i; update tallest.
3. Reverse the indices.

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        view = []
        tallest = 0  # highest building to the right so far
        for i in range(len(heights) - 1, -1, -1):
            if heights[i] > tallest:
                view.append(i)  # nothing to its right blocks the view
            tallest = max(tallest, heights[i])
        return view[::-1]  # increasing order

What the code is doing, line by line:

1. A building is blocked only by an equal or taller building on its right, which is exactly the running maximum.
2. Indices are collected right to left, so they're reversed at the end.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Strictly decreasing → all indices.
• Equal heights (only the last one sees).
• One building.

Complexity: O(n) time, O(1) extra space (besides the answer).

Problem: For each element, return the second element to its right that is greater than it (or −1).

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Scanning right for each element is O(n²); two stacks are O(n).

Spot it: Next Greater Element with a twist: after an index finds its first greater element it waits for a second. Keep two monotonic decreasing stacks: s1 (no greater seen yet) and s2 (one seen). A new value first resolves s2, then moves resolved items from s1 into s2.

Why not another pattern? Scanning right for each element is O(n²); a heap-based version is O(n log n).

Approach:

1. For each x: pop from s2 while nums[top] < x → their answer is x.
2. Pop from s1 while nums[top] < x into a temporary list (they just met their first greater).
3. Push that list onto s2 in its original order (keeps s2 decreasing); push i onto s1.

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        answer = [-1] * len(nums)
        s1 = []  # indices still waiting for their first greater element
        s2 = []  # indices that saw one greater element, waiting for the second
        for i, x in enumerate(nums):
            while s2 and nums[s2[-1]] < x:
                answer[s2.pop()] = x  # second greater found
            moved = []
            while s1 and nums[s1[-1]] < x:
                moved.append(s1.pop())  # x is their first greater
            s2.extend(reversed(moved))  # keep s2 in decreasing order of value
            s1.append(i)
        return answer

What the code is doing, line by line:

1. Both stacks hold indices with decreasing values from bottom to top, so pops always take the smallest waiting values first.
2. x is checked against s2 before the moved items join it, so it can't count as both their first and second greater.
3. The popped items came off s1 from smallest value upward; reversing restores bottom-to-top decreasing order.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal values (not greater).
• Decreasing array → all −1.
• Second greater far away.

Complexity: O(n) time (each index moves through each stack once), O(n) space.

Problem: The min-product of a subarray is min · sum. Return the maximum over all subarrays (mod 10⁹ + 7, after maximising).

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁷

From brute force to the pattern: All subarrays: O(n²); stack boundaries + prefix sums: O(n).

Spot it: Fix the minimum: with all values positive, the best subarray where a[i] is the minimum is the widest one, bounded by the nearest smaller elements (a monotonic stack). Its sum comes from a prefix sum.

Why not another pattern? Trying every subarray is O(n²).

Approach:

1. Find left[i] and right[i] (nearest strictly smaller) with a stack.
2. Candidate: a[i] · (P[right[i]] − P[left[i] + 1]).
3. Take the max, then mod.

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        P = [0] * (n + 1)
        for i, x in enumerate(nums):
            P[i + 1] = P[i] + x
        left, right = [-1] * n, [n] * n
        stack = []
        for i, x in enumerate(nums):
            while stack and nums[stack[-1]] > x:
                right[stack.pop()] = i  # first smaller to the right
            left[i] = stack[-1] if stack else -1  # nearest not-greater to the left
            stack.append(i)
        best = max(nums[i] * (P[right[i]] - P[left[i] + 1]) for i in range(n))  # widest range where nums[i] is the min
        return best % (10**9 + 7)

What the code is doing, line by line:

1. Positive values mean a wider subarray with the same minimum always has a bigger sum.
2. Using ≤ on the left can shorten some ranges for ties, but the tied element with the widest range still gets the full one, so the maximum is found.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal (whole array).
• Single element.
• Max before the mod (compare first, mod after).

Complexity: O(n) time and space.

Problem: Remove every node that has a strictly greater value somewhere to its right.

Solve it on LeetCode ↗

Constraints: The number of the nodes in the given list is in the range [1, 10⁵]. · 1 ≤ Node.val ≤ 10⁵

From brute force to the pattern: Pairwise checks are O(n²); the stack is O(n).

Spot it: "Is there a greater element to the right?" is the monotonic stack question. Keep surviving nodes non-increasing; a larger value removes the smaller ones before it.

Why not another pattern? Checking each node against everything after it is O(n²).

Approach:

1. Walk the list; pop nodes with a smaller value than the current node.
2. Push the current node.
3. Relink the stack's nodes in order.

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        stack = []
        node = head
        while node:
            while stack and stack[-1].val < node.val:
                stack.pop()  # a greater value appears to its right: remove it
            stack.append(node)
            node = node.next
        for a, b in zip(stack, stack[1:]):
            a.next = b  # relink the survivors
        stack[-1].next = None
        return stack[0]

What the code is doing, line by line:

1. After the walk, the stack holds exactly the nodes with nothing greater to their right, in order.
2. Equal values stay (only strictly greater removes).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already non-increasing (unchanged).
• Increasing list (only the last stays).
• Equal values.

Complexity: O(n) time, O(n) space (reversing the list twice gives O(1)).

Problem: Starting from zeros, each operation adds 1 to a subarray. Return the fewest operations to reach target.

Solve it on LeetCode ↗

Constraints: 1 ≤ target.length ≤ 10⁵ · 1 ≤ target[i] ≤ 10⁵ · The input is generated such that the answer fits inside a 32 bit integer.

From brute force to the pattern: Repeated range increments are O(n · max); summing rises is O(n).

Spot it: Think of the operations as layers of a skyline (the monotonic stack view): when the height rises, new layers must start; when it falls, some layers end. So the answer is target[0] plus every positive rise.

Why not another pattern? Simulating with repeated range increments is O(n · max).

Approach:

1. ops = target[0].
2. For each i ≥ 1: add max(0, target[i] − target[i − 1]).

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        ops = target[0]  # layers needed for the first column
        for prev, cur in zip(target, target[1:]):
            ops += max(0, cur - prev)  # only a rise needs new layers
        return ops

What the code is doing, line by line:

1. Operations covering position i − 1 can extend to i for free while the height doesn't rise.
2. Each unit of rise must begin a new operation, and that's enough.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal → that value.
• Strictly decreasing → target[0].
• Single element.

Complexity: O(n) time, O(1) space.

Problem: Sum min(sub) · sum(sub) over all subarrays (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: 1 ≤ strength.length ≤ 10⁵ · 1 ≤ strength[i] ≤ 10⁹

From brute force to the pattern: All subarrays: O(n²). Stack + double prefix sums: O(n).

Spot it: Like Sum of Subarray Minimums: each element is the minimum of the subarrays whose ends lie in (left[i], right[i]) from a monotonic stack. Here each such subarray is weighted by its sum, and all those sums together come from a prefix sum of prefix sums.

Why not another pattern? Enumerating subarrays is O(n²) with n = 10⁵.

Approach:

1. left[i]: previous index with a smaller value (strict); right[i]: next index with a smaller or equal value (ties counted once).
2. P = prefix sums, PP = prefix sums of P.
3. Contribution of i: a[i] · ((PP[r+1] − PP[i+1]) · (i − l) − (PP[i+1] − PP[l+1]) · (r − i)).

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        MOD = 10**9 + 7
        a, n = strength, len(strength)
        left, right = [-1] * n, [n] * n
        stack = []
        for i in range(n):
            while stack and a[stack[-1]] >= a[i]:
                right[stack.pop()] = i  # next smaller-or-equal
            left[i] = stack[-1] if stack else -1  # previous strictly smaller
            stack.append(i)
        P = [0] * (n + 1)  # P[k] = a[0] + ... + a[k-1]
        for i, x in enumerate(a):
            P[i + 1] = P[i] + x
        PP = [0] * (n + 2)  # PP[k] = P[0] + ... + P[k-1]
        for k in range(n + 1):
            PP[k + 1] = PP[k] + P[k]
        total = 0
        for i in range(n):
            l, r = left[i], right[i]
            ends = (PP[r + 1] - PP[i + 1]) * (i - l)  # sum of P[y+1] over right ends, once per left end
            starts = (PP[i + 1] - PP[l + 1]) * (r - i)  # sum of P[x] over left ends, once per right end
            total += a[i] * (ends - starts)
        return total % MOD

What the code is doing, line by line:

1. Subarray [x, y] has sum P[y + 1] − P[x]. Summing over all x in (l, i] and y in [i, r) splits into a sum of P[y + 1] (counted i − l times) minus a sum of P[x] (counted r − i times).
2. Both sums are ranges of P, so the prefix sums of P answer them in O(1).
3. Strict on one side and non-strict on the other assigns each subarray to exactly one minimum.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal values (ties).
• Single element → a².
• Large values (mod).

Complexity: O(n) time and space.

Problem: Jump forward 1 to k steps from index 0 to the last index; maximise the sum of visited values.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length, k ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Checking k predecessors is O(nk); the deque is O(n).

Spot it: dp[i] needs the maximum of the previous k dp values → a sliding window maximum with a monotonic deque.

Why not another pattern? Scanning k previous values per index is O(n · k).

Approach:

1. dp[0] = nums[0]; deque holds indices with decreasing dp.
2. Drop indices older than i − k; dp[i] = nums[i] + dp[front].
3. Pop smaller dp values from the back; push i.

from collections import deque

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        window = deque([0])  # indices with decreasing dp values
        for i in range(1, len(nums)):
            if window[0] < i - k:
                window.popleft()  # too far back to jump from
            dp[i] = nums[i] + dp[window[0]]  # best place to jump from
            while window and dp[window[-1]] <= dp[i]:
                window.pop()  # never better than i again
            window.append(i)
        return dp[-1]

What the code is doing, line by line:

1. The deque front is always the best dp within the last k indices.
2. Each index enters and leaves the deque once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k ≥ n (jump straight).
• Negative values.
• k = 1 (visit everything).

Complexity: O(n) time, O(k) space.