This lesson on Stacks, Queues & Monotonic Stack is hands-on and example-driven. You will identify and implement monotonic stack patterns to solve next/previous greater or smaller element problems. By storing array indices and maintaining strict element ordering, you will optimize brute-force quadratic searches down to linear time.

What You'll Be Able To Do

• Differentiate between monotonic increasing and monotonic decreasing stacks based on problem requirements.
• Implement the four-step generic monotonic stack template using index storage.
• Transform brute-force O(N^2) element lookup routines into amortized O(N) algorithms.
• Calculate index-based offsets and distances like wait times in temperature lookups.
• Adapt comparison predicates to alternate between next greater and next smaller element searches.

Detailed Concept Walkthrough

1. Monotonic Stack Fundamentals

A monotonic stack is a specialized stack that preserves elements in strictly increasing or strictly decreasing order throughout iteration. It provides immediate access to the nearest boundary element without scanning backward repeatedly.

• Mechanism: A monotonic decreasing stack keeps elements in descending order to find the next greater element, while a monotonic increasing stack keeps elements in ascending order to find the next smaller element.
• Execution Flow: As you iterate through an array, any new element that violates the monotonicity property triggers the eviction and processing of smaller/larger elements currently sitting on the stack.
• Under the Hood: Elements are only removed when a definitive boundary (a greater or smaller value) is discovered, resolving pending queries in a single pass.

# Monotonic Decreasing Stack Property Example
# Stack stores values in decreasing order: [73, 71, 69]
# Incoming element 72 violates order for 69 and 71
stack = [73, 71, 69]
incoming = 72
while stack and stack[-1] < incoming:
    popped = stack.pop()  # 69 is popped, next greater is 72

Key Takeaway: Use decreasing stacks to find next greater elements and increasing stacks to find next smaller elements.

2. Generic Template and Index Storage

The standard monotonic stack algorithm follows a four-step sequence (Initialize, Loop, Pop Violations, Push) while storing array indices rather than raw values.

• Syntax Rule: Always store the current element's index i on the stack instead of nums[i], giving simultaneous access to both positions and values.
• Execution Flow: For each element, run a while loop that checks whether the stack is non-empty and whether the current element violates the ordering relative to nums[stack[-1]].
• Best Practice: Pre-allocate a result array initialized with default fallback values (such as -1 or 0) so unpopped elements are handled automatically.

def monotonic_template(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # Stores indices
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            prev_index = stack.pop()
            result[prev_index] = nums[i]
        stack.append(i)
    return result

Key Takeaway: Storing indices instead of raw values unlocks positional calculations without sacrificing value lookups.

3. Amortized Linear Complexity Proof

Despite the nested while loop inside the main iteration, monotonic stack algorithms execute in strict O(N) amortized time.

• Mechanism: Every index in the array is pushed onto the stack exactly once during the outer for loop.
• Under the Hood: An index can be popped from the stack at most once across the entire algorithm run, capping total pop operations at N.
• Runtime Analysis: Because the total number of push and pop operations across all iterations cannot exceed 2N, the aggregate runtime scales linearly as O(N).

# Operations breakdown for an array of size N:
# Total Pushes: Exactly N
# Total Pops: At most N
# Total Comparisons inside while: <= 2N
# Time Complexity: O(N) amortized
# Space Complexity: O(N) for stack and result arrays

Key Takeaway: Monotonic stack runtime is strictly O(N) because each item enters and exits the stack at most once.

4. Positional Differences in Daily Temperatures

When a problem requires measuring the distance between elements rather than their values, the popped index is subtracted from the current index.

• Mechanism: When processing a warmer day at index i, pop the colder day's index prev_i and record i - prev_i into the result array.
• Syntax Rule: Initialize the result array with 0 so that any days that never see a warmer temperature default to zero days waited.
• Best Practice: Always reference temperatures[stack[-1]] inside the loop condition to evaluate values while maintaining the index on the stack.

def daily_temperatures(temperatures):
    res = [0] * len(temperatures)
    stack = []  # indices of unresolved colder days
    for i, temp in enumerate(temperatures):
        while stack and temp > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            res[prev_idx] = i - prev_idx  # Days waited
        stack.append(i)
    return res

Key Takeaway: Calculate element distances directly by taking the difference between the current index and the popped index.

Topics Covered in Stacks, Queues & Monotonic Stack

1. Rationale and Complexity (0:00 - 0:19) — Explains how monotonic stacks reduce array search problems from quadratic to linear time.
2. Stack Types Defined (0:19 - 0:54) — Defines increasing and decreasing monotonic stacks and maps them to target problems.
3. Generic Template (0:54 - 1:13) — Introduces the four-step algorithmic template and highlights storing indices over values.
4. Next Greater Element (1:13 - 3:10) — Demonstrates solving the Next Greater Element problem and proves amortized linear runtime.
5. Template Adaptation (3:10 - 3:15) — Shows how reversing the comparison operator adapts the stack to find smaller elements.
6. Daily Temperatures Study (3:15 - 4:07) — Applies index subtraction on a decreasing stack to compute wait times between days.
7. Practice and Next Steps (4:07 - 4:22) — Provides guidance on locating curated problem sets to master monotonic stack patterns.

DSA for Interviews Cheat Sheet

• Monotonic Decreasing Stack — Finds next greater elements in O(N)

  while stack and nums[i] > nums[stack[-1]]:
      result[stack.pop()] = nums[i]
  

• Monotonic Increasing Stack — Finds next smaller elements in O(N)

  while stack and nums[i] < nums[stack[-1]]:
      result[stack.pop()] = nums[i]
  

• Index Storage Push — Records current index for future resolution

  stack.append(i)
  

• Index Distance Calculation — Measures gap between current and previous element

  result[prev_idx] = i - prev_idx
  

Comparison Table

Common Pitfalls

• Mistake: Storing raw values instead of indices in the stack. Avoid: Push array indices to enable distance calculations and original array lookups.
• Mistake: Assuming nested loops imply O(N^2) time complexity. Avoid: Recognize that each element is pushed once and popped at most once, guaranteeing O(N).
• Mistake: Using an increasing stack when searching for greater elements. Avoid: Use a decreasing stack for greater elements and an increasing stack for smaller ones.

FAQs

• Why does a nested while loop inside a for loop run in O(N) time? Every array element is pushed onto the stack exactly once and popped at most once. The total number of stack operations across all iterations is bounded by 2N.
• How do I handle elements that have no next greater or smaller element? Initialize your output array with default fallback values like -1 or 0 before running the loop. Elements remaining on the stack at the end will retain these defaults.
• Can a monotonic stack find previous greater or smaller elements? Yes. When an element is pushed, the item directly beneath it on the stack represents its previous greater or smaller element depending on stack ordering.

Stack and Queue Fundamentals: Course Supplement

The existing video focuses on monotonic stacks. This companion establishes the ordinary stack and queue interfaces first; it does not claim that the video teaches every operation below.

Stack: last in, first out

Use a Python list with append and pop() at the end. These operations are amortized O(1). A stack is useful when the most recently discovered unfinished item must be handled next: nested delimiters, iterative DFS, undo histories, and monotonic-stack patterns.

stack = []
stack.append("open")
top = stack[-1] if stack else None
item = stack.pop() if stack else None

Check emptiness before reading or removing the top. A stack traversal must record enough state to resume after visiting a child.

Queue: first in, first out

Use collections.deque; append at the right and popleft at the left are O(1). A queue is the natural frontier for level-order traversal and unweighted shortest paths.

from collections import deque

queue = deque([start])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in seen:
            seen.add(neighbor)
            queue.append(neighbor)

Mark nodes seen when they are enqueued, so multiple parents cannot add duplicate pending work. Do not use list.pop(0) for a queue: it shifts the remaining elements and costs O(N) per removal.

Monotonic stack preview

A monotonic stack stores candidate indices in nondecreasing or nonincreasing value order. When a new value makes the top candidate permanently irrelevant, pop it and resolve its answer. Each index is pushed once and popped at most once, giving O(N) total time. Decide whether equal values should stay or pop based on whether the task asks for a strictly greater/smaller value or allows equality.

Use a normal stack or queue when order alone is the requirement; use a monotonic stack only when a future element can permanently resolve earlier candidates.