Knowledge Guide
Home › DSA

Advanced Patterns

Step 21 in the DSA path · 17 concepts · 55 problems

0 / 72 complete

📘 Learn Advanced Patterns from zero

The Monotonic Stack/Queue pattern keeps elements in a stack in sorted (here, increasing) order so you can answer "for each element, what is the nearest smaller/greater neighbor?" in O(n) total. The trigger: you're iterating an array and for each element you need the previous-less-element (PLE) and next-less-element (NLE) boundaries — exactly what Sum of Subarray Minimums needs. For each value, count how many subarrays it dominates as the minimum: left * right * value, where left = distance to PLE and right = distance to NLE. To avoid double-counting subarrays when equal values appear, we break ties asymmetrically: the left boundary uses strictly-less (pop on >=) and the right boundary uses less-or-equal (pop on >), so each subarray is attributed to exactly one minimum.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Setup & the goal
arr = [ 3 , 1 , 2 , 4 ]
idx     0   1   2   3

stack (indices, values increasing): []
ans = 0    MOD = 1e9+7

For each element we want:
  left[i]  = # of choices for subarray start (incl. i)
  right[i] = # of choices for subarray end   (incl. i)
contribution = arr[i] * left[i] * right[i]

Goal: sum of min over every contiguous subarray. Brute force is O(n^2). Instead, each element arr[i] is the minimum of exactly left[i]*right[i] subarrays — those bounded by its nearest smaller neighbors. Why a monotonic stack: it finds those nearest-smaller boundaries for all i in one pass.

Step 2 — Push index 0 (value 3)
arr = [ 3 , 1 , 2 , 4 ]
         ^i=0
stack top has nothing smaller below it.

While stack && arr[stack.top] >= 3:  (empty -> skip)
left[0] = i - (-1) = 1   (no PLE; sentinel -1)
push -> stack = [0]      (values: [3])

Stack is empty, so index 0 has no previous-less element; its left boundary is the array edge. left[0]=1 means only one subarray can start here with 3 as a candidate min: [3] itself. We pop on >= for the left side so the PLE is strictly-less, the convention that keeps equal values from being double-counted.

Step 3 — Process index 1 (value 1): pop 3
arr = [ 3 , 1 , 2 , 4 ]
             ^i=1
While stack && arr[stack.top]=3 >= 1:  POP index 0
  -> 3's right boundary is fixed: NLE of 3 is index 1.
stack now empty.
left[1] = i - (-1) = 2   (1 has no smaller element to its left)
push -> stack = [1]      (values: [1])

Value 1 is smaller than 3, so 3 can never be the min of any subarray extending past index 1 — we pop it, finalizing that 3's reach to the right ends here. left[1]=2: subarrays starting at index 0 or 1 can have 1 as min, since everything to the left (just 3) is larger.

Step 4 — Process index 2 (value 2)
arr = [ 3 , 1 , 2 , 4 ]
                 ^i=2
While stack && arr[stack.top]=1 >= 2?  1 >= 2 is FALSE -> stop.
PLE of 2 is index 1 (value 1).
left[2] = i - 1 = 1
push -> stack = [1, 2]   (values: [1, 2])

The stack top is 1, which is smaller than 2, so we stop popping — 1 is the previous-less element of 2. left[2]=1: only a subarray starting exactly at index 2 keeps 2 as min, because index 1 holds the smaller 1.

Step 5 — Process index 3 (value 4)
arr = [ 3 , 1 , 2 , 4 ]
                     ^i=3
While stack && arr[stack.top]=2 >= 4?  FALSE -> stop.
PLE of 4 is index 2 (value 2).
left[3] = i - 2 = 1
push -> stack = [1, 2, 3]   (values: [1, 2, 4])

Stack stays increasing [1,2,4]. 4 is the largest so far, its previous-less element is 2 at index 2, giving left[3]=1. The main loop ends; remaining stack elements never got popped, meaning their next-less-or-equal element is the right edge (sentinel n=4).

Step 6 — Flush stack: assign right boundaries
n = 4. Survivors on the stack reach the right edge (NLE = n = 4).
right[i] = NLE[i] - i.
  popped value 3: NLE was set to index 1  -> right[0] = 1 - 0 = 1
  survivor 1 (idx 1): NLE = 4            -> right[1] = 4 - 1 = 3
  survivor 2 (idx 2): NLE = 4            -> right[2] = 4 - 2 = 2
  survivor 4 (idx 3): NLE = 4            -> right[3] = 4 - 3 = 1

idx:    0    1    2    3
val:    3    1    2    4
left:   1    2    1    1
right:  1    3    2    1

Survivors 1,2,4 never found an element <= themselves to their right, so they extend to the array's end (index 4). Popped value 3 got right=1 when index 1 popped it. Why this is safe: each element's right reach stops at the first element that is less-or-equal (or the edge), while its left reach stops at the first strictly-smaller element, so no subarray is counted under two different minima.

Step 7 — Compute contributions & total
Boundaries (PLE strictly-less on left, NLE <= on right):
idx:        0    1    2    3
val:        3    1    2    4
left:       1    2    1    1
right:      1    3    2    1
contrib = val*left*right:
  3*1*1 = 3
  1*2*3 = 6
  2*1*2 = 4
  4*1*1 = 4
--------------------------
sum = 3 + 6 + 4 + 4 = 17

Cross-check by listing every subarray min of [3,1,2,4]: 3, 1, 2, 4 (len1) + min(3,1)=1, min(1,2)=1, min(2,4)=2 (len2) + min(3,1,2)=1, min(1,2,4)=1 (len3) + min(3,1,2,4)=1 (len4) = (3+1+2+4) + (1+1+2) + (1+1) + 1 = 10 + 4 + 2 + 1 = 17. Matches. Each element was pushed and popped once, so total work is O(n).

🎯 Guided practice

  1. Easy — Count Elements With Maximum Frequency. Given nums = [1,2,2,3,1,4], return the total count of all elements that share the highest frequency.

    Step 1 — tally: walk once, building freq = {1:2, 2:2, 3:1, 4:1}.

    Step 2 — find the max frequency: scan the values → max is 2.

    Step 3 — sum the counts of every key that hits the max: keys 1 and 2 both have count 2, so total = 2 + 2 = 4. Answer: 4.

    Pattern: a single counting pass plus a one-line reduction. O(n) time, O(k) space. The trap is returning the number of keys (2) instead of the sum of their counts (4) — re-read what's asked.

  2. Medium — Least Number of Unique Integers after K Removals. Given arr = [4,3,1,1,3,3,2], k = 3, remove exactly k elements to minimize the remaining distinct count.

    Step 1 — tally: freq = {4:1, 3:3, 1:2, 2:1} → 4 distinct values.

    Step 2 — greedy insight: to eliminate a whole distinct value cheaply, spend removals on the values with the smallest counts first — each fully-cleared value drops the distinct count by one at least cost.

    Step 3 — sort counts ascending: [1, 1, 2, 3].

    Step 4 — spend k greedily: remove count-1 → k=2, distinct=3; remove count-1 → k=1, distinct=2; next is count-2 but only k=1 left, so it survives. Answer: 2.

    Pattern: counting + greedy on sorted frequencies. Tally O(n); sorting distinct counts O(k log k). Pitfall: partially removing a value wastes removals without lowering the distinct count, so only commit removals that fully clear a value.

  3. Medium — Longest Subarray with Absolute Diff ≤ Limit (monotonic queue). Given nums = [8,2,4,7], limit = 4, find the longest window where max − min ≤ 4.

    Step 1 — two deques of indices: maxDq (values decreasing front→back) and minDq (values increasing), plus a left pointer l = 0.

    Step 2 — extend right, maintaining monotonicity: at each r, pop the back of maxDq while it's smaller than nums[r] and the back of minDq while it's larger, then push r. The fronts now give the window's max and min in O(1).

    Step 3 — shrink when invalid: while nums[maxDq.front] − nums[minDq.front] > limit, advance l and pop any deque front whose index < l.

    Step 4 — trace: r=0 [8] ok len1; r=1 [8,2] diff 6>4 → shrink to [2] len1; r=2 [2,4] diff 2 ok len2; r=3 [2,4,7] diff 5>4 → shrink to [4,7] diff 3 ok len2. Answer: 2.

    Pattern: sliding window + monotonic deques storing indices. Each index enters and leaves each deque once → O(n) total, O(n) space. Pitfall: storing values instead of indices, which leaves you unable to evict elements that slid past l.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic