001 Notes

Sequential Aggregation Professional Playbook

Overview and Reading Path

Sequential aggregation solves problems by scanning data in a deliberate order while maintaining a small summary of what has been seen.

Use this family when the answer comes from:

moving pointers through an array or string
growing and shrinking a contiguous window
comparing prefix summaries
counting frequencies or keyed states
merging sorted streams
maintaining a monotonic stack or queue

Read in this order:

Identify the scan order.
Define the maintained summary.
State the invariant after each update.
Decide when the answer updates.
Pick the specific strategy.

Core Vocabulary

Term	Meaning
Scan order	The order in which elements are processed
Summary	The compact information kept from processed elements
Invariant	The fact that stays true after each update
Window	A contiguous active range of the input
Pointer	An index that marks a scan position or boundary
Prefix	Aggregate information from the beginning up to a position
Candidate	An item still able to affect the answer

Beginner Mental Model

Think of reading a long receipt from left to right.

You do not want to reread the receipt for every question. Instead, you keep a small notebook:

current total
items in current window
counts seen so far
best answer so far
useful candidates still waiting

Sequential aggregation is the skill of choosing what goes in that notebook.

The whole pattern is:

read next item
update the notebook
remove anything no longer valid
update the answer

From Brute Force To This Pattern

Brute force repeatedly asks the same question from scratch:

for every index:
    rescan earlier values
    recompute the same counts, sums, or candidates

Sequential aggregation changes the question:

After I scan one more item, how should my compact memory change?

That is the shift from repeated rescanning to one-pass memory maintenance.

What Information Becomes Reusable

Reusable information is the part of the past that can still affect the future:

a running sum
a prefix count
a frequency map
the left boundary of a valid window
unresolved indexes in a monotonic stack
candidate maximums in a monotonic queue

Everything else should be forgotten. A good sequential solution is often a controlled forgetting process.

What This Mental Model Prevents

This model prevents:

nested rescans that should be one pass
updating the answer before the window is valid
keeping expired elements in a queue
storing all history when only counts or candidates matter
using sliding window when negative numbers break monotonic shrinking

Small Visual Model

processed past        current       unseen future
[facts compressed] -> nums[i] -> [not inspected yet]
        |
        `-- summary must contain everything future steps need

What This Family Is / Is Not

Use this family when the input can be processed in a stable order and a compact summary is enough.

Do not use it when:

the answer requires exploring many choices
the problem has arbitrary graph reachability
the subproblem state repeats in a DP-like way
sorting or heap ordering is the real reason the solution works

Universal Template

initialize summary
initialize answer

for each scan position:
    add new information
    remove expired or invalid information
    restore invariant
    update answer

return answer

Core Mental Model

The key question is:

What do I know after processing this prefix, window, stream, or frontier?

Sequential aggregation is not about trying choices. It is about preserving the useful facts from a scan so the next answer update is cheap.

The universal shape is:

summary = empty
answer = neutral value

for item in scan order:
    add item to summary
    restore invariant
    update answer from summary

Every sequential solution has five contracts:

scan order:
    the exact order in which items become visible

summary:
    the facts remembered from processed items or the current window

enter rule:
    how the next item changes the summary

leave rule:
    whether and how old information is removed

answer update:
    the exact moment when the summary represents a valid candidate

How To Read This Family Visually

Use the same symbols throughout this section:

[]    active window, current prefix, unresolved stack, or deque contents
{}    stored summary: counts, prefix map, stack, deque, running value
^     current item, pointer, window boundary, or stream head
-->   scan movement, enter, leave, pop, or merge advance
x     expired, invalid, dominated, or no longer useful
==    equivalent prefix/summary relation
...   processed or unprocessed stream section

One-minute mental model:

see a one-way scan
    -> ask what the summary knows after each step
    -> add entering information and remove stale information
    -> update only when the invariant is true
    -> invariant: summary exactly describes the current prefix/window/frontier

Read every diagram as:

shape:
    what scan order is being used?
memory:
    what summary is kept instead of raw history?
action:
    what enters, leaves, or gets popped?
invariant:
    why is the answer update now valid?

ASCII Visual Map

Sequential aggregation should feel like a conveyor belt: information enters, stale information leaves if needed, and the answer is updated only when the summary is truthful.

prefix summary:

index:        0    1    2    3    4
value:        a    b    c    d    e
prefix:   0  | a |a+b|...|

range [l, r] is answered from two remembered prefix facts.

sliding window:

          left                 right
           v                     v
array:  [  .   .   .   .   .   .   .  ]
              <--- current window --->

step:
    add nums[right]
    while invalid: remove nums[left], left++
    update answer when window is valid

monotonic stack:

incoming value = 73

stack before:  [80, 75, 70, 68]
                         ^   ^
                         popped because 73 is warmer

stack after:   [80, 75, 73]

Popped items have found their next greater/warmer value.

monotonic queue for window maximum:

window indexes:      2   3   4   5
values:              1   9   4   7

deque indexes:           [3, 5]
deque values:            [9, 7]

Front is the best valid candidate; expired indexes leave from the front.

answer timing:

expand -> repair -> update

right enters summary
        |
        v
restore invariant
        |
        v
summary now describes a valid candidate
        |
        v
update answer

Scan Order

Most bugs start with an unclear scan order.

Problem shape	Scan order
two pointers	one or two monotonic pointer movements
sliding window	right pointer expands, left pointer repairs validity
prefix sum	left to right over indexes
merge technique	smallest next item among sorted streams
monotonic stack	left to right or right to left depending on nearest relation
monotonic queue	right pointer enters, expired left indexes leave
interval intersection	advance the interval with smaller end

Problem Shape Diagrams

two pointers:

left                                      right
 v                                          v
[ 2 ][ 4 ][ 6 ][ 8 ][ 9 ][ 11 ][ 15 ][ 20 ]

Move one pointer using a proof that skipped pairs cannot win.
invariant: moved pointer cannot participate in a better skipped answer

sliding window:

              left              right
               v                  v
[ . ][ . ][   current window   ][ . ][ . ]

right expands; left shrinks until the invariant is restored.
invariant: summary describes exactly the current valid window

prefix sum:

array:    [a] [b] [c] [d] [e]
prefix: 0  |a|a+b|...|
             ^       ^
             l      r+1

range fact = prefix[r + 1] - prefix[l]
invariant: prefix[i] stores the aggregate before index i

merge technique:

A:  1   4   8
    ^
B:  2   3   9
    ^

Compare current heads, consume the smaller useful item.
invariant: consumed stream item is the next globally usable item

monotonic stack:

scan --->  5   3   4   2   6

stack before 6: [5, 4, 2]
pop dominated:     2, 4, 5
stack after 6:  [6]

Pops answer nearest-greater/smaller questions.
invariant: stack keeps only unresolved useful candidates

monotonic queue:

window values:  [1, 9, 4, 7]
deque values:      [9, 7]
                    ^
                  max

Back removes dominated values; front removes expired indexes.
invariant: deque front is the best valid candidate in the window

interval intersection:

A: [----]      [------]
B:    [---]  [----]
        ^^     ^^
     overlap  overlap

Advance the interval with the smaller end.
invariant: the smaller-ending interval cannot overlap future intervals more

The scan order is a proof that no skipped position needs to be reconsidered. If pointers can move backward, this family may not be the right model.

Summary Meaning

The summary is the compressed memory of the scan.

Strategy	Summary
two pointers	current endpoints and any running measure
sliding window	counts, sum, distinct count, or matched characters in window
prefix sum + hashing	running prefix plus previous prefix frequencies/indexes
counting + hashing	frequency table of processed items
merge technique	current positions in each sorted stream
monotonic stack	unresolved useful candidates in monotonic order
monotonic queue	best candidate indexes for the current window

A summary is complete when it contains everything needed for the next update. It is minimal when it does not store raw history that will never be queried.

Enter and Leave Mechanics

Every scanned item either accumulates forever, enters a window temporarily, or becomes a candidate that may be dominated.

prefix-only:
    information only enters

moving window:
    information enters on the right and leaves on the left

monotonic structure:
    new information removes dominated old candidates

merge scan:
    one stream position advances after the current comparison

Leaving is as important as entering. A sliding window count that never removes left-side characters is no longer describing the current window.

Invariant Before Answer Update

The invariant decides when the summary is safe to use.

Problem	Invariant before update
longest substring without repeat	window has no duplicate characters
minimum size subarray sum	window sum is at least target before shrinking update
subarray sum equals k	map stores prefixes before current index is counted
daily temperatures	stack is decreasing by temperature
sliding window maximum	deque front is inside window and greatest value
container with most water	moving shorter side cannot miss better area

Some problems update before repair, some after repair, and some during repair. Write that timing down before coding.

Prefix vs Window vs Candidate Memory

Do not force all scans into sliding windows.

Need	Model
range answer from difference of two earlier totals	prefix summary
contiguous valid region that can shrink	sliding window
nearest greater/smaller unresolved item	monotonic stack
min/max over moving fixed-size range	monotonic queue
matching pairs/groups in processed values	counting map
sorted lists consumed in order	merge technique

The sign of numbers is a major clue. Variable-size sum windows rely on monotonic growth, so negative numbers often push the solution toward prefix sums or monotonic queues.

Universal Sequential Template

initialize summary and answer

for item or pointer position in scan order:
    incorporate entering information
    remove expired, invalid, or dominated information
    restore the invariant required by this strategy
    if the summary now represents a valid candidate:
        update the answer

return answer, transformed array, or final summary

Strategy-Specific Mental Model

Strategy	Mental model	Main risk
two pointers	pointer movement discards impossible pairs	moving the wrong side
sliding window	window is repaired until valid	answer update timing
prefix sum + hashing	previous prefixes complete current ranges	storing latest when earliest is needed
counting + hashing	frequency table represents processed portion	stale counts
merge technique	sorted streams expose next usable item	advancing wrong stream
monotonic stack	stack keeps unresolved useful candidates	popping equal values incorrectly
monotonic queue	deque front is best valid window candidate	not expiring old indexes

Mini Traces

Trace 1: sliding window repair.

target: no duplicate characters

step 1:
    window = [a b c]
    counts = {a:1, b:1, c:1}
    invariant: window has no duplicates

step 2:
    add b -> [a b c b]
    counts = {a:1, b:2, c:1}
    invariant broken: b appears twice

step 3:
    remove from left until valid -> [c b]
    counts = {c:1, b:1}
    invariant: window has no duplicates again

Trace 2: monotonic stack.

scan temperatures:
70, 68, 73

step 1:
    stack = [70, 68]
    invariant: unresolved temperatures are decreasing

step 2:
    see 73
    pop 68, then pop 70
    invariant: popped indexes have found their next warmer day

step 3:
    push 73
    stack = [73]
    invariant: stack is decreasing again

Contrast Diagrams

Sliding window vs prefix sum:

sliding window:
    [current contiguous valid region]
       left ------------ right
    invariant: summary describes only the current window

prefix sum:
    prefix history: P0 P1 P2 P3 P4
    range = later prefix - earlier prefix
    invariant: map/array stores reusable facts about previous prefixes

Monotonic stack vs monotonic queue:

stack:
    unresolved candidates for nearest greater/smaller
    top changes as new items dominate old ones
    invariant: order is monotonic from bottom to top

queue:
    best candidates inside a moving window
    front expires when it leaves the window
    invariant: front is best valid candidate for the current window

Misclassification Checks

Use this family when one pass plus a small summary explains the solution. Be careful when:

Symptom	Better family may be
future choices branch and repeat	State Space Exploration
the proof depends on sorted global discard	Ordered Optimization
there are many independent range queries	Range Query & Indexed Aggregation
nodes and edges define the problem	Connectivity Discovery
arithmetic identity is the main trick	Mathematical Numeric Reasoning

The clean test is: after processing item i, can you state exactly what the summary knows and why old information can be forgotten?

Detailed Translation Workflow

Translate every sequential problem in this order:

1. What is my scan order?
2. What enters the summary at each step?
3. What leaves the summary, if anything?
4. What invariant must be true before answer update?
5. What exact value updates the answer?

The most important distinction is whether the summary is prefix-only or a moving window:

prefix-only:
    information only accumulates

window:
    information enters on the right and leaves on the left

monotonic structure:
    worse candidates are discarded permanently

Strategy Map

Strategy	Use when	Maintained invariant
Two Pointers	two ends or slow/fast movement discards impossible cases	pointer movement never misses a better candidate
Sliding Window	answer lives inside a contiguous range	window is valid, or becomes valid after shrinking
Prefix Sum + Hashing	subarray answers come from differences of prefixes	map stores previous prefix summaries
Counting + Hashing	frequencies decide matches, groups, or duplicates	counts reflect processed portion
Merge Technique	sorted streams can be consumed in order	output/answer uses the next smallest available item
Monotonic Stack	need next/previous greater or smaller item	stack stores useful candidates in monotonic order
Monotonic Queue	moving window needs min/max in O(1)	front is best valid candidate

Translation Checklist

Ask these before coding:

Scan:
    What order do I process elements?

Summary:
    What facts must be kept?

Invariant:
    What is true after each step?

Update:
    When does the answer change?

Removal:
    Do elements ever leave the summary?

Problem Translation Table

Problem type	State / summary	Update rule	Engine
Container With Most Water	`left`, `right`, best area	move shorter wall	two pointers
Two Sum II	sorted endpoints	compare sum to target	two pointers
Remove Duplicates From Sorted Array	write pointer, read pointer	write unique values	slow/fast pointer
Linked List Cycle	slow and fast pointers	advance at different speeds	slow/fast pointer
Longest Substring Without Repeating	window counts/set	shrink until no duplicate	sliding window
Minimum Size Subarray Sum	window sum	shrink while sum is enough	sliding window
Permutation in String	window character counts	compare fixed-size window	sliding window
Subarray Sum Equals K	prefix sum counts	count `prefix - k`	prefix sum + hash
Continuous Subarray Sum	remainder first index	repeat remainder with length >= 2	prefix modulo hash
Product Except Self	left product, right product	combine two passes	prefix/suffix aggregation
Majority Element II	candidates and counters	Boyer-Moore cancellation	counting summary
Group Anagrams	character-count key	append word by signature	counting + hashing
Merge Sorted Array	three write pointers	write larger tail value	merge technique
Interval List Intersections	two interval pointers	advance earlier-ending interval	merge technique
Daily Temperatures	decreasing index stack	pop warmer resolved days	monotonic stack
Largest Rectangle in Histogram	increasing stack	pop bars when boundary found	monotonic stack
Sliding Window Maximum	decreasing deque	expire old, pop worse	monotonic queue
Shortest Subarray With Sum At Least K	prefix deque	maintain increasing prefixes	monotonic queue

Canonical Examples

Two Pointers: Container With Most Water

Invariant:

All containers discarded by moving the shorter side cannot beat the current
candidate with that same side.

Skeleton:

def max_area(height):
    left = 0
    right = len(height) - 1
    best = 0

    while left < right:
        width = right - left
        best = max(best, width * min(height[left], height[right]))

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

Sliding Window: Longest Substring Without Repeating

Invariant:

s[left:right + 1] contains no repeated character.

Skeleton:

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0

    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)

    return best

Prefix Sum + Hashing: Subarray Sum Equals K

Invariant:

counts[p] is how many earlier prefixes had sum p.

Skeleton:

from collections import defaultdict


def subarray_sum(nums, k):
    counts = defaultdict(int)
    counts[0] = 1
    prefix = 0
    ans = 0

    for value in nums:
        prefix += value
        ans += counts[prefix - k]
        counts[prefix] += 1

    return ans

Monotonic Stack: Daily Temperatures

Invariant:

The stack contains unresolved days with temperatures in decreasing order.

Skeleton:

def daily_temperatures(temperatures):
    ans = [0] * len(temperatures)
    stack = []

    for day, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev = stack.pop()
            ans[prev] = day - prev
        stack.append(day)

    return ans

Monotonic Queue: Sliding Window Maximum

Invariant:

The deque stores indexes in decreasing value order, and the front is inside
the current window.

Skeleton:

from collections import deque


def max_sliding_window(nums, k):
    dq = deque()
    ans = []

    for i, value in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= value:
            dq.pop()
        dq.append(i)

        if i >= k - 1:
            ans.append(nums[dq[0]])

    return ans

Decision Rules

Use two pointers when sorted order or endpoint movement lets you discard a side. Use sliding window when the target object is contiguous and the window can be repaired by moving left. Use prefix sums when the answer for a subarray depends on prefix[j] - prefix[i]. Use counting when value frequencies are the real state. Use a monotonic stack when a future element resolves previous elements. Use a monotonic queue when a moving window needs the best candidate.

Common Failure Modes

Moving both pointers when only one side has been proven discardable.
Treating a non-contiguous subsequence problem as a sliding window.
Updating answer before restoring the window invariant.
Forgetting counts[0] = 1 in prefix-count problems.
Storing values instead of indexes in monotonic structures when expiration or distance matters.
Popping equal values incorrectly when duplicates change the answer.

Performance Notes

Most sequential aggregation solutions are O(n) because each item enters and leaves the maintained structure at most once.

Cache behavior is usually good because scans are linear. Hash maps and deques add overhead but avoid nested loops. SIMD is most realistic for numeric scans and prefix-style operations, but correctness usually comes from the invariant, not vectorization.

Cheat Sheet

Two pointers:
    What side can be discarded?

Sliding window:
    What makes the window valid?
    When do I shrink?

Prefix sum:
    What previous prefix would complete the answer?

Counting:
    What key groups equal states?

Monotonic stack:
    What does the current item resolve?

Monotonic queue:
    What candidates are expired or worse?

Extended Translation Notes

Sequential aggregation problems usually fail when the maintained summary is vague. Use this workflow to make the summary concrete before writing code.

Step 1: Decide the Scan Unit

Ask what one iteration consumes.

Examples:

Surface	Scan unit
array	one index
string	one character
sorted intervals	one interval
sorted arrays	one head from either stream
monotonic stack	one current item that may resolve previous items
monotonic queue	one index entering a moving window

The scan unit determines when data enters the maintained summary.

Step 2: Decide What Can Leave

Some scans only add information. Others also remove old information.

Pattern	Add	Remove
Prefix sum	current value	never
Counting prefix	current key	never
Sliding window	right value	left values until valid
Fixed window	new right value	expired left value
Monotonic stack	current index	worse unresolved indexes
Monotonic queue	current index	expired indexes and worse back indexes

If elements leave the summary, write the removal rule before coding the answer update.

Step 3: State the Invariant

The invariant should be short enough to say out loud.

Good examples:

The window has no duplicate characters.
The map contains counts of prefixes before the current index.
The stack contains unresolved decreasing temperatures.
The deque front is the maximum inside the current window.

Bad examples:

The window is correct.
The stack has useful things.
The map stores stuff.

Vague invariants lead to off-by-one and update-order bugs.

Step 4: Place the Answer Update

There are three common placements:

after adding current item
after restoring validity
after resolving previous candidates

Examples:

Sliding window maximum updates after the window reaches size k.
Longest substring updates after duplicates are removed.
Daily Temperatures updates while popping unresolved colder days.
Prefix count problems update before inserting the current prefix if the subarray must end at the current index and start earlier.

Strategy Invariants

Two Pointers

Two pointers are about controlled discard.

The proof must explain why moving one pointer cannot remove the optimal answer.

Common movement rules:

Situation	Move
sorted sum too small	move left forward
sorted sum too large	move right backward
container area	move shorter wall
remove duplicates	advance read, write only accepted values
linked-list cycle	slow moves one, fast moves two

Sliding Window

Sliding window works when a contiguous range can be repaired by moving one side.

Flexible window:

expand right
while invalid:
    shrink left
update answer

Fixed window:

add right
if size > k:
    remove left
if size == k:
    update answer

Do not use sliding window for non-contiguous subsequences.

Prefix Sum + Hashing

Prefix hashing works because every subarray sum is a difference:

sum(i..j) = prefix[j + 1] - prefix[i]

For target k, when current prefix is p, a previous prefix p - k completes the answer.

The order matters:

answer += counts[current_prefix - k]
counts[current_prefix] += 1

This prevents counting an empty subarray unless the problem allows it.

Monotonic Stack

A monotonic stack stores candidates whose answer is not known yet.

When the current item makes top candidates useless or resolved, pop them.

Typical questions:

next greater element
previous smaller element
largest rectangle
remove digits for smallest number

The stack is usually not all previous items. It is the compressed set of previous items still capable of affecting the answer.

Monotonic Queue

A monotonic queue is a monotonic stack plus expiration.

It supports moving-window best values:

pop front while expired
pop back while worse than current
push current
front is the best valid candidate

Indexes are usually better than values because indexes tell you when an item expires.

Worked Problem Snapshots

Remove Duplicates From Sorted Array

State:

read = current scan index
write = next position for unique value

Invariant:

nums[0:write] contains the unique values from nums[0:read].

Trap:

Do not append to a new list if the problem requires in-place mutation.

Move Zeroes

State:

write = next position for a nonzero value

Invariant:

nums[0:write] contains all nonzero values seen so far in original order.

Trap:

Preserve relative order of nonzero elements.

Minimum Size Subarray Sum

State:

left, right, window_sum

Invariant:

After shrinking, window_sum is either below target or left is the smallest
start that was not yet proven too short.

Trap:

Only works with positive numbers because shrinking has monotonic behavior.

Permutation in String

State:

fixed-size window counts

Invariant:

The window length equals len(pattern) before comparing counts.

Trap:

Remove zero-count keys if dictionary equality is used.

Continuous Subarray Sum

State:

first_index_by_remainder

Invariant:

If a remainder repeats far enough apart, the subarray between them is divisible
by k.

Trap:

Store the first occurrence, not the latest, to maximize length.

Majority Element II

State:

two candidate slots and their counters

Invariant:

Cancellation removes triples of distinct values without changing possible
majorities over n/3.

Trap:

Verify candidates in a second pass.

Interval List Intersections

State:

i, j over two sorted interval lists

Invariant:

The interval with the earlier end cannot intersect future intervals from the
other list after this step.

Trap:

Advance by end time, not start time.

Largest Rectangle in Histogram

State:

increasing stack of bar indexes

Invariant:

Bars in the stack have not yet found a right boundary smaller than themselves.

Trap:

Add a sentinel zero height to flush the stack.

Shortest Subarray With Sum At Least K

State:

deque of prefix indexes with increasing prefix sums

Invariant:

Earlier worse prefixes are removed because a later smaller prefix is always
better.

Trap:

This is not a normal sliding window when numbers can be negative.

Dry Runs

Dry Run: Prefix Sum Count

Input:

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

Process:

start: prefix = 0, counts = {0: 1}, ans = 0

value 1:
    prefix = 1
    need = -2
    ans += 0
    counts[1] = 1

value 2:
    prefix = 3
    need = 0
    ans += 1
    counts[3] = 1

value 1:
    prefix = 4
    need = 1
    ans += 1
    counts[4] = 1

Answer:

Dry Run: Daily Temperatures

Input:

temperatures = [73, 74, 75, 71]

Process:

day 0, 73: stack = [0]
day 1, 74: pop 0, answer[0] = 1, stack = [1]
day 2, 75: pop 1, answer[1] = 1, stack = [2]
day 3, 71: no pop, stack = [2, 3]

Unresolved days keep answer 0.

Dry Run: Sliding Window Maximum

Input:

nums = [1, 3, 2, 5]
k = 2

Deque process:

i=0 value=1: dq=[0]
i=1 value=3: pop 0, dq=[1], answer 3
i=2 value=2: dq=[1,2], answer 3
i=3 value=5: expire 1, pop 2, dq=[3], answer 5

Answer:

[3, 3, 5]