Shelf · DSA Patterns · Chapter 4

Chapter 4: Linear patterns

Most array and list questions are a single pass with a little carried state. This chapter gives you the six scan shapes (pointers, windows, prefix sums, fast/slow, interval merge, cyclic placement) and, for each, the invariant that proves it correct and the precondition that breaks it.

Difficulty
Priority
dsa-04-01Card 1 of 6

Two pointers and safe in-place movement

MediumP2 · Very likelyKnow cold8 min
two-pointersin-placeinvariantcompaction

Why you care

On the job, "rewrite this buffer without allocating a second copy" shows up whenever a batch is big enough that a copy hurts: dropping voided rows, deduplicating a sorted extract, splitting a file into good and bad. Interviewers ask two-pointer questions because they expose whether you can state what each pointer promises, not whether you remember a trick. The usual failure is overwriting a value you have not read yet. This card comes before windows because windows are two pointers with a running aggregate attached.

Explain like I'm 5

Picture a conveyor belt with a packer. A reader walks along the belt looking at every item. A writer stands at the start of a clear shelf and only moves forward when the reader hands over an item worth keeping. The shelf is the front of the same belt, so the writer can never get ahead of the reader. The reader has already looked at anything the writer is about to overwrite.

Core concept

Two pointers are two indices with a written promise about the region each has finished.

  • Opposing pointers start at both ends and move inward. They need a proof for discarding: on sorted input, if the pair sum is too small, the left element is too small for every remaining partner. Without order there is no such proof.
  • Same-direction pointers (reader and writer) keep one invariant: xs[:w] is the answer so far, xs[w:r] is overwritable, xs[r:] is unread. Since w <= r, a write never destroys unread data.
  • Cost: each pointer moves forward at most n times, so O(n) time and O(1) extra space. Derive it from movement, not loop syntax.
  • State your mutation permission. After in-place compaction the tail beyond w is stale.

Decision rule: use opposing pointers when sortedness proves which end to discard; use reader/writer to filter, dedupe or partition in place. For unsorted pairs use a set (Hash maps and sets under stated assumptions).

Minimal example Write pointer compaction

Pythonruns
def compact(xs, drop):
    w = 0
    for r in range(len(xs)):
        if xs[r] != drop:
            xs[w] = xs[r]
            w += 1
    return w

orders = [5, 0, 7, 0, 0, 9]
n = compact(orders, 0)
print(n, orders[:n])
print(orders)
Output
3 [5, 7, 9]
[5, 7, 9, 0, 0, 9]

The second line is the lesson: the list is not shortened, and its tail still holds old values. Return the count and let the caller slice.

In production Opposing-pointer scan and in-place filter

Pythonruns
from itertools import pairwise

def assert_sorted(xs):
    if any(a > b for a, b in pairwise(xs)):
        raise ValueError("input must be sorted ascending")

def converge_on_total(amounts, target):
    """Opposing pointers on sorted input: indices i < j with sum == target."""
    assert_sorted(amounts)
    lo, hi = 0, len(amounts) - 1
    while lo < hi:
        s = amounts[lo] + amounts[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1      # amounts[lo] is too small for every remaining hi
        else:
            hi -= 1      # amounts[hi] is too big for every remaining lo
    return None

def keep_in_place(rows, keep):
    """Same-direction pointers: stable, in place. Returns the kept count."""
    w = 0
    for r in range(len(rows)):
        if keep(rows[r]):
            rows[w] = rows[r]
            w += 1
    return w

debits = [120, 250, 400, 650, 900]
print(converge_on_total(debits, 1050))
print(converge_on_total(debits, 100))
try:
    converge_on_total([900, 120, 400], 1020)
except ValueError as e:
    print(f"ValueError: {e}")
batch = [("o1", "paid"), ("o2", "void"), ("o3", "paid"), ("o4", "void"), ("o5", "paid")]
n = keep_in_place(batch, lambda row: row[1] == "paid")
del batch[n:]
print(batch)
Output
(2, 3)
None
ValueError: input must be sorted ascending
[('o1', 'paid'), ('o3', 'paid'), ('o5', 'paid')]

The sortedness check costs O(n), the same order as the search, so keep it in production code and drop it only when a caller contract guarantees order.

See it happen Reader and writer on one list

orders (list)579009
  1. The reader and writer both start at index 0; 5 is kept, so it is copied onto itself and the writer moves to 1.
  2. The reader sees 0, a dropped value, so the writer stays at slot 1, which is now the next target.
  3. The reader finds 7 and writes it into slot 1; the 0 that lived there was already read, so nothing is lost.
  4. The reader reaches 9 at index 5 and writes it into slot 2, after skipping two more zeros.
  5. The writer is at 3, so slots 0 to 2 are the answer and slots 3 to 5 are stale leftovers, not cleared values.
Notice: the writer never passes the reader, which is why overwriting is safe.
Scenario A

In your world

The situation

A Jenkins job loads a 2M-row orders extract into a list and drops voided rows with for i, o in enumerate(orders): if o.void: orders.pop(i).

What actually breaks

Popping while iterating skips the row that slides into the freed slot, so 41,870 voided rows of 312,904 survive. Each pop also shifts the tail, so the step is quadratic.

What you'd do on Monday

Use the reader/writer pass: copy kept rows forward, then del orders[w:]. Assert that no kept row is void and log kept and dropped counts to the audit table.

Scenario B

Imagine you work at Amazon

40M catalogue rows compacted nightly

The numbers

40M rows × ~120 B ≈ 4.8 GB raw, about 16 GB as Python tuples. Dropping 25% with del rows[i] on 1M-row chunks shifts ~3.2 MB per drop: 250k drops × ~0.3 ms ≈ 75 s per chunk, 40 chunks ≈ 50 min. A write-pointer pass is 40M steps × ~0.15 µs ≈ 6 s.

What the Scenario-A answer does here

The Scenario A fix (reader/writer) is still the right loop, but it assumes the list fits in memory. At 16 GB it does not.

What flips at this scale

The pointers become a read cursor and a write cursor over chunk files of 1M rows (~400 MB). Survivors are appended to an output object, so memory is bounded by the chunk and the invariant is unchanged.

The trade-off you'd defend

I would defend chunked streaming filters over one giant in-place pass, trading the strict O(1) extra-space guarantee for a bounded buffer and a second output file that makes retries safe.

Illustrative figures chosen so the arithmetic is visible; not Amazon-published.

Gotchas

Overwriting a value you have not read

Symptom

After a partition, one value is missing and another appears twice.

Cause

The writer got ahead of the reader, or a swap lost the displaced value.

Fix

Write what xs[:w], xs[w:r] and xs[r:] mean first, and assert w <= r.

Trusting the tail after compaction

Symptom

Downstream sees [5, 7, 9, 0, 0, 9] and loads 6 rows instead of 3.

Cause

In-place compaction leaves stale values past w.

Fix

del xs[w:], or pass xs[:w].

Tricky questions

Is a loop inside a loop over the pointers quadratic?
Most people say

There is a while inside a for, so it is O(n squared).

Actually

Count movement. If each pointer only moves forward and never resets, the total is at most 2n moves, whatever the syntax.

Scenario question

You're handed a sorted list of 5M settlement amounts and must find a pair of amounts whose total matches a reconciliation figure, without extra memory.

Model answer

I'd use opposing pointers: if the sum is too small the left value is too small for every remaining partner, so I advance it. That is O(n) time and O(1) space. The trade-off is that I rely on sortedness, so I'd verify it once. For unsorted data I'd take a set and pay O(n) memory.

Interview corner

CommonWhen do you reach for two pointers?
“I'd use them when I can write down what each pointer guarantees: on sorted data I discard an end with a proof, and for in-place filtering I keep a reader and a writer.”
TrickIs this nested loop O(n squared)?
“I'd count pointer movement, not loops. Each pointer moves forward at most n times and never resets, so it is O(n).”
Experience checkTell me about a time you cleaned data in place.
“I removed voided orders with a write pointer instead of popping in a loop, which turned a timing-out step into one pass, and I logged kept and dropped counts for the audit table.”

Memory hook

Reader looks at everything; writer only advances for keepers; the writer never passes the reader.

If you remember only one thing:

Write down what the region behind each pointer means before you write the loop.

Self-check

  1. Why is overwriting safe in reader/writer?

    Because w <= r, every slot the writer touches was already read.

  2. Why do opposing pointers need sorted input?

    The discard proof depends on order.

  3. Time and space of a two-pointer pass?

    O(n) time, O(1) extra space.

Prove it

Take a 200,000-element list where every 4th item is "void". Time pop(i)-based removal against keep_in_place with time.perf_counter, and paste both timings plus an assertion that the kept lists are equal.

dsa-04-02Card 2 of 6

Fixed sliding windows

EasyP2 · Very likelyKnow cold7 min
sliding-windowfixed-widthrolling-aggregate

Why you care

Rolling metrics are everywhere in data work: error rate over the last 5 minutes, 7-day moving average, the busiest hour in a day. Recomputing each window from scratch costs O(n times k), which is fine for k=5 and a disaster for k=1,440. Interviewers use the fixed window as the gentlest test of incremental thinking: do you update, or recompute? The failures they watch for are evaluating before the window is full and slicing for every position.

Explain like I'm 5

You are counting people in a train carriage with exactly k seats. When the train moves one stop, one person gets on and one gets off. You do not recount everyone. You add the person who boarded and subtract the one who left, and you only announce the count once the carriage is full.

Core concept

Per element: add the entering item, remove the leaving item (xs[i - k]), evaluate once i >= k - 1.

  • The aggregate must update in O(1): sum, count, sum of squares. A median or max needs extra structure such as a deque (Monotonic stacks and queues).
  • Evaluate only when the window is full; earlier reports partial windows as full ones.
  • Define the edges: empty input, k <= 0 and k > n have no valid window. Return empty or raise, and say which.
  • Cost: O(n) time; the n - k + 1 results count as output space (Account for auxiliary and output space).

Decision rule: fixed window when the size is given and the metric is additive; variable window (Variable sliding windows) when you search for the size; prefix sums (Prefix sums and range accounting) for many arbitrary ranges.

Minimal example Rolling sum

Pythonruns
def window_sums(xs, k):
    if k <= 0 or k > len(xs):
        return []
    total, out = 0, []
    for i, x in enumerate(xs):
        total += x
        if i >= k:
            total -= xs[i - k]
        if i >= k - 1:
            out.append(total)
    return out

print(window_sums([4, 1, 3, 2, 6], 3))
print(window_sums([4, 1], 3), window_sums([], 2), window_sums([1, 2], 0))
Output
[8, 6, 11]
[] [] []

Five items and k=3 give three windows: n - k + 1. The second line shows the three edge cases returning an empty result by choice.

In production Error-rate windows with an oracle

Pythonruns
import random

def flag_windows(errors, requests, k, pct):
    """Start minutes of k-minute windows whose error rate exceeds pct percent."""
    if len(errors) != len(requests):
        raise ValueError("errors and requests differ in length")
    if not 1 <= k <= len(errors):
        raise ValueError(f"window k={k} outside 1..{len(errors)}")
    e = r = 0
    flagged = []
    for i in range(len(errors)):
        e += errors[i]
        r += requests[i]
        if i >= k:
            e -= errors[i - k]
            r -= requests[i - k]
        if i >= k - 1 and r and e * 100 > pct * r:
            flagged.append(i - k + 1)
    return flagged

def brute(errors, requests, k, pct):
    out = []
    for s in range(len(errors) - k + 1):
        e, r = sum(errors[s:s + k]), sum(requests[s:s + k])
        if r and e * 100 > pct * r:
            out.append(s)
    return out

errs = [0, 1, 0, 9, 12, 2, 0, 0]
reqs = [100, 100, 90, 120, 110, 100, 0, 0]
print(flag_windows(errs, reqs, 3, 5))
for bad_k in (0, 9):
    try:
        flag_windows(errs, reqs, bad_k, 5)
    except ValueError as exc:
        print(f"ValueError: {exc}")
rng = random.Random(7)
bad = 0
for _ in range(300):
    n = rng.randint(1, 12)
    q = [rng.randint(0, 50) for _ in range(n)]
    x = [rng.randint(0, v) for v in q]
    k = rng.randint(1, n)
    bad += flag_windows(x, q, k, 10) != brute(x, q, k, 10)
print("mismatches:", bad)
Output
[2, 3, 4]
ValueError: window k=0 outside 1..8
ValueError: window k=9 outside 1..8
mismatches: 0

Two details matter. The test e * 100 > pct * r uses integers, so no float rounding decides a boundary window. And the brute-force oracle checks 300 random cases against the incremental version, which is how you prove an O(1)-update loop has no off-by-one.

See it happen One enters, one leaves

minutes41326running total11
  1. At i=0 the item 4 enters and the total is 4; only one of three seats is filled, so nothing is reported.
  2. At i=1 the item 1 enters and the total is 5; the carriage is still not full.
  3. At i=2 the item 3 enters, the total is 8, and the window is valid for the first time, so 8 is reported.
  4. At i=3 the item 2 enters and the item 4 leaves, so the total becomes 6 with two O(1) operations.
  5. At i=4 the item 6 enters and the item 1 leaves, giving 11; the work per step never grew with k.
Notice: the report starts at the third step, not the first.
Scenario A

In your world

The situation

A pipeline computes a 7-day rolling average of daily load counts per supplier with sum(counts[i-7:i]) / 7 for every day.

What actually breaks

For the first days i-7 is negative, so the slice is empty or wraps; the audit table shows averages far too low for new suppliers and the build stays green.

What you'd do on Monday

Add day i, subtract day i-7, emit only when i >= 6. Return NULL for incomplete windows, count how many suppliers were skipped, and add the brute-force comparison as a unit test.

Scenario B

Imagine you work at Slack

5-minute and 24-hour message-rate windows per channel

The numbers

2M active channels. Recomputing a 24-hour window (k=1,440 minute buckets) each minute costs 2M × 1,440 ≈ 2.9B adds. The incremental update is 2 operations per channel, or 4M per minute. Ring buffers of 1,440 counters × 4 B × 2M channels ≈ 11.5 GB.

What the Scenario-A answer does here

The Scenario A fix (add entering, subtract leaving) is still the right per-channel update. What it hides is that subtracting needs the leaving item, so state is O(k) per key, and 11.5 GB does not fit in one process.

What flips at this scale

Shard the ring buffers by channel id, for example 16 shards ≈ 720 MB each, and store per-minute buckets, not raw events. Late events need a watermark or a write to the correct bucket, or the total silently drifts.

The trade-off you'd defend

I would defend per-key incremental windows over recomputation, trading about 11.5 GB of state and a lateness policy for a 700x cut in work per tick (2.9B vs 4M).

Illustrative figures for arithmetic; not Slack-published.

Gotchas

Reporting before the window is full

Symptom

The first k-1 outputs are suspiciously low, such as a 7-day average of 2.4 on day 1.

Cause

Evaluation ran at every index instead of when i >= k - 1.

Fix

Guard the evaluation with the width condition.

Removing the wrong index

Symptom

Totals drift and never match a brute-force recompute.

Cause

The leaving item is xs[i - k], not xs[i - k + 1] or xs[i - k - 1].

Fix

Check k=1 on paper, then compare with a brute-force oracle.

Tricky questions

Does a slice-per-window version have the same cost?
Most people say

sum(xs[i:i+k]) is one line and one loop, so it is O(n).

Actually

Each slice copies and sums k items, so the total is O(n times k).

Scenario question

You're handed per-second request counts and asked for the peak 10-minute total of the day. Someone proposes sorting each window.

Model answer

I'd keep a running total over 600 seconds, add the new second, subtract the one 600 back, and track the max once 600 values exist. That is O(n) with O(k) memory. The trade-off is that I must retain raw seconds; if memory were tight I'd bucket to minutes and accept coarser alignment.

Interview corner

CommonHow does a fixed sliding window beat brute force?
“I'd update the aggregate instead of recomputing it: add the entering element, remove the leaving one, evaluate once the window is full. That is O(n) instead of O(n times k).”
TrickDoes it work for any statistic?
“I'd say no. It works when the update is O(1), like sum or count. For a median or max I need a heap or a monotonic deque, so the cost changes.”
Experience checkWhere have you used a rolling metric?
“I computed a 7-day average per supplier and found it was wrong for new suppliers because it evaluated before seven days existed. I gated output on a full window and added a brute-force test.”

Memory hook

Add the one who boards, subtract the one who leaves, speak only when the carriage is full.

If you remember only one thing:

Evaluate only after the window is full, and only if the update is O(1).

Self-check

  1. Which index leaves the window at step i?

    i - k.

  2. When do you first evaluate?

    When i >= k - 1.

  3. Why is slicing each window not O(n)?

    Each slice-and-sum is O(k), so the total is O(n times k).

Prove it

Implement window_sums and a slicing version. Run both on 1,000,000 integers with k=1,000 using time.perf_counter, and paste both timings plus an assertion that the outputs match.

dsa-04-03Card 3 of 6

Variable sliding windows

MediumP2 · Very likelyKnow cold8 min
sliding-windowvariable-widthinvariantfrequency-state

Why you care

Real data questions are often "the longest stretch where something stays true": a run without a failure, a session that touched at most three stores. As nested loops they cost O(n squared) and time out on production sizes. Interviewers pick variable windows because the pattern is easy to recite and easy to misuse: it works only under a monotone property, and many candidates apply it where shrinking throws away answers.

Explain like I'm 5

A rubber band stretched along a row of beads. Pull the right hand forward to take another bead. If the band now holds something illegal, release beads from the left until it is legal again. Each hand only moves forward, and you note the size whenever the band is legal.

Core concept

Template: expand right, restore the invariant by shrinking left, then evaluate.

  • Write the invariant first: "at most k distinct merchants" or "sum within budget".
  • Shrink monotonicity: removing from the left can only keep the window legal or move it toward legal. That holds for non-negative sums and distinct-count limits. It fails with signed values, where a too-big window may become valid after a later negative.
  • Frequency state: keep a Counter and delete a key when its count hits zero, or len(counts) overstates the distinct count and the shrink loop never ends.
  • Cost: right moves n times and left at most n times, so O(n) pointer moves plus the cost of each state update, O(1) average for dict operations (Hash maps and sets under stated assumptions).

Decision rule: variable window when the property is monotone under shrinking and the run is contiguous; prefix-state lookup (Prefix sums and range accounting) when negatives are possible.

Minimal example A budget window that negatives break

Pythonruns
def longest_within(xs, limit):
    best = total = left = 0
    for right, x in enumerate(xs):
        total += x
        while total > limit and left <= right:
            total -= xs[left]
            left += 1
        best = max(best, right - left + 1)
    return best

xs = [3, 4, -5, 1]
print(longest_within(xs, 2))
print(max((j - i for i in range(4) for j in range(i + 1, 5) if sum(xs[i:j]) <= 2), default=0))
Output
2
3

The window reports 2 while brute force finds 3 (the first three values sum to 2). Shrinking threw away the 3 and 4 that the later -5 would have rescued.

In production At most k distinct merchants, with cleanup

Pythonruns
from collections import Counter
import random

def longest_run(merchants, k, cleanup=True):
    """Longest contiguous run touching at most k distinct merchants: (length, start)."""
    if k < 1:
        raise ValueError("k must be >= 1")
    counts = Counter()
    left = best_len = best_start = 0
    for right, m in enumerate(merchants):
        counts[m] += 1
        while len(counts) > k:           # invariant broken: shrink until restored
            gone = merchants[left]
            counts[gone] -= 1
            if cleanup and counts[gone] == 0:
                del counts[gone]
            left += 1
        if right - left + 1 > best_len:
            best_len, best_start = right - left + 1, left
    return best_len, best_start

def brute(ms, k):
    return max((j - i for i in range(len(ms)) for j in range(i + 1, len(ms) + 1)
                if len(set(ms[i:j])) <= k), default=0)

events = ["m1", "m1", "m2", "m3", "m2", "m2", "m1", "m4", "m4"]
print(longest_run(events, 2))
try:
    longest_run(events, 2, cleanup=False)
except IndexError as e:
    print(f"IndexError: {e}")
rng = random.Random(3)
bad = 0
for _ in range(300):
    ms = [rng.choice("abcd") for _ in range(rng.randint(1, 10))]
    k = rng.randint(1, 3)
    bad += longest_run(ms, k)[0] != brute(ms, k)
print("mismatches:", bad)
Output
(4, 2)
IndexError: list index out of range
mismatches: 0

With cleanup=False dead keys keep len(counts) above k forever, so left runs off the end of the list.

See it happen Expand, break, shrink, evaluate

events (k=2)abaccdistinct in window2
  1. Right takes a at index 0; the window holds 1 distinct value, which is within the limit of 2.
  2. Right takes b at index 1; two distinct values is still legal.
  3. Right takes a again; the window [0..2] is legal with length 3.
  4. Right takes c; distinct jumps to 3 and the invariant is broken, so evaluation must wait.
  5. Left drops index 0 (a still occurs at 2) and then index 1 (b hits zero and its key is deleted); distinct is 2 again.
  6. Right takes c at index 4; the window [2..4] is legal with length 3, tying the best so far.
Notice: the invariant is broken for exactly one frame, and shrinking runs until it is legal before any length is recorded.
Scenario A

In your world

The situation

A Jenkins job scans a sorted event feed per rider and flags the longest stretch touching at most 3 distinct pickup zones, checking every start and end pair with len(set(events[i:j])).

What actually breaks

A rider with 1,000 events has ~500k start/end pairs, each building a set over ~330 items on average: 1,000³ / 6 ≈ 1.7×10^8 element touches. Across 300 riders that is 5×10^10, and at ~50 ns each about 2,500 s (42 minutes), which sometimes hits the Jenkins timeout with no partial output.

What you'd do on Monday

Port the window with a Counter, delete zones at zero, record length after the shrink loop, and keep the quadratic version as a test oracle.

Scenario B

Imagine you work at Zepto

900M rider events a day

The numbers

1.5M riders × ~600 events ≈ 900M events a day. A window scan is up to 900M right moves plus 900M left moves ≈ 1.8B steps. At ~0.5 µs per step that is ~900 s of CPU, about 28 s across 32 workers. A quadratic scan is 600² / 2 ≈ 180k pairs per rider × 1.5M = 270B checks.

What the Scenario-A answer does here

The Scenario A fix (one pass with a counter) still works per rider. What breaks is the assumption that each rider's events arrive together and in order: a raw feed interleaves riders and delivers late pings.

What flips at this scale

Partition by rider id, then sort each partition by timestamp. Sorting 600 events is about 600 × log2(600) ≈ 5,500 comparisons, about 4 to 5 times the ~1,200-step scan itself, so ordering becomes the dominant cost, and the window state stays at most k+1 keys.

The trade-off you'd defend

I would defend partition, sort, then scan over a global sort, trading a shuffle by rider for tiny sorts and O(k) window state.

Illustrative volumes and per-step timings; not Zepto-published.

Gotchas

Shrinking on data with negative values

Symptom

The window returns 2 where a brute-force check returns 3, with no error.

Cause

A sum-driven shrink loop assumes removing the left element cannot hurt. With negatives, a too-big window can become valid later, so shrinking discards valid candidates.

Fix

For signed values use prefix-state lookup (Prefix sums and range accounting).

Counter keys left at zero

Symptom

IndexError: list index out of range.

Cause

counts[x] -= 1 leaves the key at 0, so len(counts) never drops below k+1.

Fix

Delete the key at zero.

Tricky questions

Is a while loop inside a for loop quadratic here?
Most people say

The shrink loop can run many times per step, so O(n squared).

Actually

left only moves forward, at most n times in total, so the pointers cost O(n) amortized (Complexity and amortization).

Scenario question

You're handed hourly signed adjustments (credits and debits) and asked for the longest period whose net stays under a limit. A teammate has a working window on last month's positive-only data.

Model answer

I'd refuse to reuse it: with negatives, shrinking on "sum over limit" discards candidates a later credit would fix. I'd move to prefix sums, which do not rely on monotonicity. An exact-net target is an O(n) dict lookup; a "stays under a limit" target needs a sorted or prefix-min search, O(n log n). The trade-off is that extra log factor plus the prefix array's memory.

Interview corner

CommonHow do you know a variable window is valid?
“I'd state the invariant and check that removing from the left can only move toward legal. That holds for non-negative sums or a distinct-count limit, not for signed values.”
TrickWhy is it O(n) with a loop inside a loop?
“I'd say each pointer moves forward at most n times, so it is at most 2n steps.”
Experience checkDescribe a bug you hit with stateful scans.
“I once left zero-count keys in a counter, so the distinct count never fell and the shrink ran past the end. I now delete at zero and test against a brute-force oracle.”

Memory hook

Stretch right, release left until legal, then measure.

If you remember only one thing:

Shrinking is valid only if removing from the left can never make a legal answer impossible.

Self-check

  1. What are the three steps per right index?

    Add the element, shrink while the invariant is broken, then evaluate.

  2. Why delete a Counter key at zero?

    Otherwise len(counts) overstates the distinct count.

  3. Why does signed data break a sum window?

    A later negative can make a discarded start valid again.

Prove it

Run longest_within against brute force on 500 seeded random lists (length up to 8, values -5 to 5). Paste the first mismatch and the count, then repeat with values 0 to 5 and show zero.

dsa-04-04Card 4 of 6

Prefix sums and range accounting

MediumP2 · Very likelyKnow cold7 min
prefix-sumsrange-queriespreprocessinghalf-open

Why you care

Dashboards and reconciliations ask for totals over arbitrary date ranges: "net for days 40 to 75", repeated thousands of times. Summing each range costs O(range) per query; one preprocessing pass makes every query O(1). Interviewers ask for this because it tests whether you separate preprocessing from query cost, and whether you handle boundaries cleanly. Off-by-one errors in range sums are the most common bug in this area, and the leading zero plus half-open ranges removes most of them.

Explain like I'm 5

Think of a taxi meter. The meter shows the cumulative fare from the start. To find what the middle of the trip cost, read the meter at the end and at the start and subtract. You never re-add each kilometre. The meter shows 0 before the trip starts, and that zero is what lets "from the very beginning" work like any other range.

Core concept

  • Build prefix with a leading identity: prefix[0] = 0, prefix[i+1] = prefix[i] + xs[i]. Its length is n + 1.
  • Use half-open ranges: the sum of xs[lo:hi] is prefix[hi] - prefix[lo]. The empty range returns 0 with no special case, and adjacent ranges never overlap.
  • Cost: O(n) preprocessing, O(n) storage, O(1) per query. It pays off only with many queries.
  • It is static: changing xs[d] makes every later prefix stale, so an update is an O(n) rebuild.
  • Prefix-state lookup is a second use: store earlier prefix values in a dict and look up prefix[hi] - target. Unlike a window, it works with negative values.

Decision rule: prefix sums for repeated additive range queries on rarely changing data, or exact-target spans on signed values; a window for one sweep with a size or validity rule. Neither works for max or min, which have no subtraction.

Minimal example Leading zero and half-open ranges

Pythonruns
from itertools import accumulate

sales = [5, 3, 8, 2, 6]
prefix = [0, *accumulate(sales)]

def range_sum(lo, hi):          # half-open [lo, hi)
    return prefix[hi] - prefix[lo]

print(prefix)
print(range_sum(1, 4), range_sum(0, 5), range_sum(2, 2))
Output
[0, 5, 8, 16, 18, 24]
13 24 0

range_sum(1, 4) is 18 - 5 = 13: items 1, 2 and 3. The whole array and the empty range both work without a branch.

In production Ledger queries and earliest-index lookup for an exact net

Pythonruns
from itertools import accumulate

class Ledger:
    """Static daily net amounts (credits minus debits, may be negative)."""
    def __init__(self, nets):
        self.prefix = [0, *accumulate(nets)]    # prefix[i] = sum(nets[:i])

    def total(self, lo, hi):
        """Net over days [lo, hi); hi is exclusive."""
        n = len(self.prefix) - 1
        if not 0 <= lo <= hi <= n:
            raise IndexError(f"range [{lo}, {hi}) outside 0..{n}")
        return self.prefix[hi] - self.prefix[lo]

    def widest_span_for_net(self, target):
        """Longest [lo, hi) whose net equals target, or None. One pass, O(n) extra."""
        first = {}                              # prefix value -> earliest index
        best = None
        for hi, p in enumerate(self.prefix):
            lo = first.get(p - target)          # look up before inserting: no empty span
            if lo is not None and (best is None or hi - lo > best[1] - best[0]):
                best = (lo, hi)
            first.setdefault(p, hi)
        return best

nets = [4, -1, -3, 5, -2, -3]
led = Ledger(nets)
print(led.prefix)
print(led.total(1, 4), led.total(0, 6), led.total(3, 3))
print(led.widest_span_for_net(0), led.widest_span_for_net(5), led.widest_span_for_net(99))
try:
    led.total(4, 9)
except IndexError as e:
    print(f"IndexError: {e}")
Output
[0, 4, 3, 0, 5, 3, 0]
1 0 0
(0, 6) (0, 4) None
IndexError: range [4, 9) outside 0..6

The span with net 0 covers all six days because the prefix returns to 0. Keeping the earliest index per prefix value gives the longest span. Inserting after the lookup is what stops an empty span from matching itself.

See it happen Build once, subtract many times

sales53826prefix058161824
  1. prefix[0] is 0, the sum of nothing; it is what lets a range that starts at the very beginning use the same formula.
  2. One left-to-right pass fills prefix[i+1] = prefix[i] + sales[i], so the build costs n additions.
  3. The query [1,4) is prefix[4] minus prefix[1], which is 18 minus 5 = 13, two reads and one subtraction.
  4. The empty query [2,2) is prefix[2] minus prefix[2] = 0, correct without any if statement.
  5. If sales[2] changes, every prefix from index 3 onward is stale; this structure suits data that has stopped moving.
Notice: a query reads two cells no matter how long the range is.
Scenario A

In your world

The situation

A Jenkins job answers finance's "net settled amount between two dates" requests for 900 merchants with one SELECT SUM(...) WHERE day BETWEEN per request, 15,000 requests a night.

What actually breaks

Each query scans about 90 days of rows, and two requests stitched at a month-end counted that boundary day in both halves. Finance sees a net 1.8 lakh off and the audit table cannot say why.

What you'd do on Monday

Load each merchant's daily nets into a prefix list once, answer with half-open total(lo, hi), stitch ranges by sharing a boundary index, and assert total(a,c) == total(a,b) + total(b,c).

Scenario B

Imagine you work at Paytm

1.2M merchants, 2M range queries a day

The numbers

1.2M merchants × 365 days × 8 B ≈ 3.5 GB of daily prefixes. Queries average 90 days: naive is 2M × 90 = 180M additions, prefix is 2M subtractions. Late corrections: 300k a day, each invalidating ~180 prefix cells on average, so rebuilding costs 54M updates a day.

What the Scenario-A answer does here

The Scenario A fix (prefix per merchant) still answers queries in O(1). What breaks is the "static" assumption: corrections arrive daily, and rebuilding the suffix after each correction wastes ~54M updates.

What flips at this scale

Freeze closed months and keep prefixes per month; rebuild only the open month (at most 31 cells, ~16 per correction). A cross-month query adds frozen month totals, which are themselves a 12-value prefix.

The trade-off you'd defend

I would defend month-partitioned prefixes over one yearly array, trading a slightly longer query (two or three boundary lookups) for correction cost bounded by 31 cells instead of 365.

Illustrative figures for arithmetic; not Paytm-published.

Gotchas

Missing leading zero

Symptom

A range starting at day 0 raises an error or returns 18 instead of 24.

Cause

prefix was built without prefix[0] = 0, so the formula needs a special case.

Fix

Build [0, *accumulate(xs)] and use prefix[hi] - prefix[lo].

Inclusive end index

Symptom

Two stitched ranges double-count the boundary day.

Cause

Closed ranges [a,b] and [b,c] both include b.

Fix

Use half-open [lo, hi) everywhere and say so in the signature.

Tricky questions

Can I use prefix sums for a range maximum?
Most people say

Same idea: a prefix maximum, then subtract.

Actually

Max has no inverse. A prefix maximum gives the best so far, not the best inside a range.

Scenario question

You're handed a daily ledger and asked to serve arbitrary date-range totals, with corrections arriving the next day.

Model answer

I'd build prefix sums for closed periods and rebuild only the open month on each correction, so queries stay O(1) and updates touch at most 31 cells. The trade-off is partition bookkeeping and a longer query. If corrections hit all history constantly I'd use a Fenwick tree or a database aggregate instead.

Interview corner

CommonWhat is a prefix sum and why add a leading zero?
“I'd define prefix[i] as the sum of the first i items with prefix[0] equal to zero. The zero makes ranges that start at the beginning work with no special case.”
TrickHow is a prefix lookup different from a sliding window?
“I'd say a window moves two pointers under a monotone rule, while a prefix lookup keeps earlier prefix values in a dict, so it still works when values are negative.”
Experience checkWhere would you use this in a data pipeline?
“I'd precompute cumulative settled amounts per merchant so finance range queries become two lookups, with half-open day indices and an assertion that stitched ranges sum to the whole.”

Memory hook

A taxi meter: read it at the end, read it at the start, subtract, and remember it starts at zero.

If you remember only one thing:

Half-open ranges plus a leading zero make every range sum two reads and one subtraction.

Self-check

  1. What is the prefix array length for n items?

    n + 1, because of the leading zero.

  2. How do you sum items lo through hi - 1?

    prefix[hi] - prefix[lo].

  3. Why is it poor for frequent updates?

    Every later prefix goes stale, so rebuilding is O(n).

Prove it

Build prefix sums over 100,000 random integers (seeded) and answer 100,000 random ranges both ways. Paste both timings with time.perf_counter and an assertion that every answer matches.

dsa-04-05Card 5 of 6

Fast and slow pointer invariants

MediumP2 · Very likelyKnow cold8 min
fast-slowlinked-listcycleidentity

Why you care

Any time you follow a "next" relation (a retry chain, a reassignment pointer, a linked structure) you can loop forever on bad data. A cycle in a config table makes a job hang with no error. Interviewers ask about fast and slow pointers because the answer shows whether you can reason about termination and O(1) space. The recurring mistakes are comparing values instead of nodes and dereferencing past the end.

Explain like I'm 5

Two runners on a track. One runs at walking speed and one at double speed. If the track is a straight line with an end, the fast runner reaches the end first and stops. If the track is a loop, the fast runner laps the slow one and they meet. That meeting proves a loop exists, without keeping a list of where either has been.

Core concept

  • The pattern needs a next relation that is deterministic and stable while you walk it.
  • Slow moves 1 hop, fast moves 2. If fast reaches the end (fast or fast.next is None) there is no cycle; if they stand on the same node there is one. Inside a loop of length L, fast gains one position per round, so they meet within L rounds.
  • Identity, not equality: compare nodes with is, never by .val.
  • Midpoint: when fast runs off the end, slow is in the middle.
  • Cycle entry: after they meet, reset one pointer to the head and move both one hop at a time; they meet at the entry.
  • Cost: O(n) steps (up to about 3n hops) and O(1) pointer state.

Decision rule: fast/slow when memory matters or you need the middle; a visited set (Hash maps and sets under stated assumptions) when next is expensive or you need the path. Neither is safe if the relation changes during the walk.

Minimal example Meeting means a loop

Pythonruns
def meets(nxt, start):
    slow = fast = start
    while fast in nxt and nxt[fast] in nxt:
        slow, fast = nxt[slow], nxt[nxt[fast]]
        if slow == fast:
            return True
    return False

print(meets({1: 2, 2: 3, 3: 4, 4: 2}, 1))
print(meets({1: 2, 2: 3, 3: 4}, 1))
print(meets({1: 1}, 1))
Output
True
False
True

The next relation is a dict from id to next id. The guard before the double hop is the termination proof; the last case is a self-loop.

In production Speed-ratio halfway and loop start on linked nodes

Pythonruns
class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def build(vals):
    head = None
    for v in reversed(vals):
        head = Node(v, head)
    return head

def halfway_by_speed(head):
    """Second middle on even length; None on empty."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def loop_start_by_reset(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                    # identity, never ==
            slow = head                     # restart one pointer at the head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

def value_compare_loop_check(head):                  # compares values: the classic mistake
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow.val == fast.val:
            return True
    return False

print(halfway_by_speed(build([1, 2, 3, 4, 5])).val, halfway_by_speed(build([1, 2, 3, 4])).val, halfway_by_speed(None))
plain = build([7, 7, 7, 7, 7, 7])
print("value-compare says cycle:", value_compare_loop_check(plain), "| identity says:", loop_start_by_reset(plain))
tail = plain
while tail.next:
    tail = tail.next
tail.next = plain.next.next                 # loop back to the node at index 2
print("entry is index 2:", loop_start_by_reset(plain) is plain.next.next)
Output
3 3 None
value-compare says cycle: True | identity says: None
entry is index 2: True

A list of six equal values has no cycle, yet the value-compare version says it does. Always compare with is.

See it happen Slow and fast meeting inside a loop

123entry45
  1. Both pointers start at the head, node 1.
  2. Round one: slow moves a single hop to node 2 and fast moves two hops to node 3.
  3. Round two: slow reaches node 3 and fast goes 3 to 4 to 5.
  4. Round three: slow reaches node 4 and fast goes 5 to 3 to 4, so both stand on the same node and a cycle exists.
  5. Slow resets to the head while fast stays at node 4; from now on both move one hop at a time.
  6. After two hops each, both stand on node 3, which is where the loop begins.
Notice: the meeting node (4) is not the entry (3); the second phase finds the entry.
Scenario A

In your world

The situation

A Jenkins job resolves "superseded by" pointers in a supplier master table. A manual edit makes SUP-114 point to SUP-209, which points back to SUP-114.

What actually breaks

The resolver loops until the build is killed after 6 hours; nothing is written and the next night's run is skipped because the lock is still held.

What you'd do on Monday

Resolve each id with fast/slow pointers over the dict, or a visited set for short chains. On a meeting, write the loop members to an invalid_chains table and continue. Add a hop cap of 1,000 as a second guard.

Scenario B

Imagine you work at Lyft

2M pending reassignment chains

The numbers

2M chains × ~20 hops = 40M next-lookups with a visited set. On an acyclic 20-hop chain fast/slow does ~30 lookups (1.5 per hop), so ~60M; looped chains cost up to ~3 per hop. At 0.3 ms per store read: 40M × 0.3 ms = 12,000 s versus 60M × 0.3 ms = 18,000 s, about 3.3 h versus 5 h.

What the Scenario-A answer does here

The Scenario A fix (fast/slow) still detects loops. What breaks is its selling point: it saves memory, but a 20-hop chain fits in a 20-entry set, and the pointers add about 50% more expensive remote reads.

What flips at this scale

When next is a remote read, the visited set wins. Use one small set per chain (about 2 KB) plus a hop cap, and snapshot the table, since a relation that changes mid-walk breaks the stability fast/slow assumes.

The trade-off you'd defend

I would defend a per-chain visited set with a hop cap over fast/slow, trading about 2 KB of transient memory per chain for a third fewer remote reads. For in-memory linked structures I would still choose fast/slow.

Illustrative volumes and latency for arithmetic; not Lyft-published.

Gotchas

Dereferencing past the end

Symptom

AttributeError: 'NoneType' object has no attribute 'next' on short lists.

Cause

Fast moved two hops without checking both fast and fast.next.

Fix

Loop on while fast and fast.next.

Comparing values instead of nodes

Symptom

A plain list of six sevens is reported as cyclic.

Cause

slow.val == fast.val compares data, which can repeat.

Fix

Compare nodes with is, or ids in a relation dict.

Tricky questions

Does the meeting node mark where the loop starts?
Most people say

The node where they meet is the cycle entry.

Actually

It is only somewhere inside the cycle. A second phase from the head finds the entry.

Scenario question

You're handed a table of 3M "replaced by" pointers from a legacy system where some chains may loop, and you must resolve every id without crashing.

Model answer

I'd load the table into a dict and resolve each chain with a hop cap and a per-chain visited set, since every step is an in-memory lookup. The trade-off is O(chain length) transient memory, which is nothing for 20 hops. For a huge linked structure where I could not hold the path I'd switch to fast/slow.

Interview corner

CommonHow do fast and slow pointers detect a cycle?
“I'd move one pointer by one hop and another by two. If the fast one hits the end there is no cycle; if they land on the same node there is, because inside a loop the fast one gains a step each round.”
TrickWhy compare nodes rather than values?
“I compare nodes because values can repeat at different positions. Only identity proves it is the same place in the structure, so I'd use is.”
Experience checkHave you hit an infinite loop in a data job?
“I hit a circular supersession chain that made a resolver run for six hours. I added loop detection plus a hop cap and sent the loop members to an exceptions table.”

Memory hook

A slow and a fast runner: the track ends, or the fast one laps the slow one.

If you remember only one thing:

Guard both fast and fast.next, and compare nodes with is.

Self-check

  1. What guard makes the double hop safe?

    while fast and fast.next.

  2. What does meeting prove?

    That a cycle exists, not where it starts.

  3. Why must the relation be stable?

    If next changes mid-walk, the pointers can miss each other.

Prove it

Build a 1,000,000-node chain with a loop at index 500,000 and one without. Run loop_start_by_reset on both, then a visited-set version under tracemalloc, and paste the entry index plus peak memory for each version.

dsa-04-06Card 6 of 6

Merge intervals and cyclic sort prerequisites

MediumP2 · Very likelyKnow cold7 min
intervalssortingcyclic-sortpreconditions

Why you care

Overlap merging is everyday ETL: sessions, maintenance windows, validity periods, outage logs. Interviewers use it to test boundary discipline: what counts as overlapping, what happens to nested spans, and whether you flush the last group. Cyclic sort is the conditional second half. It is fast only when values fit a known range, and without a guard it can loop forever.

Explain like I'm 5

Merging: lay paper strips on a table sorted by left edge. If the next strip starts before the current glued strip ends, glue it on and stretch the end if needed; otherwise lift the glued strip and start a new one. Cyclic sort: numbered mailboxes. A parcel marked 3 belongs in box 3. Keep swapping the wrong parcel out until the box holds the right one, or a duplicate you set aside.

Core concept

Merge intervals

  • Sort by start, scan once with a current [lo, hi]. If the next start is at or before hi, extend hi with max; a contained span must not shrink it.
  • Decide endpoint inclusivity: closed ends [1,3] and [3,5] merge (lo <= hi); half-open ends do not (lo < hi).
  • Flush the last group after the loop; it is still open.
  • Cost: O(n log n) for the sort plus O(n) for the scan; O(n) if already sorted.

Cyclic placement

  • Domain contract: n values, each an integer in 1..n; value v belongs at index v-1.
  • Swap a value toward its home unless the target already holds that value. Without that guard, two equal values swap forever.
  • Each swap fixes one value for good, so at most n swaps and O(n) total, but only under the stated domain.

Decision rule: merge for a union of ranges when you can afford a sort; cyclic placement only when the range contract holds and you want O(1) space.

Minimal example Sort then scan

Pythonruns
def merge(spans):
    out = []
    for lo, hi in sorted(spans):
        if out and lo <= out[-1][1]:
            out[-1][1] = max(out[-1][1], hi)
        else:
            out.append([lo, hi])
    return out

print(merge([(8, 10), (1, 3), (2, 6), (3, 4)]))
print(merge([(1, 3), (4, 5)]), merge([(1, 5), (2, 3)]), merge([]))
Output
[[1, 6], [8, 10]]
[[1, 3], [4, 5]] [[1, 5]] []

The second case, (1, 5) containing (2, 3), keeps the end at 5 because of max.

In production Explicit merge with a flush, and guarded slot placement

Pythonruns
def merge_spans(spans, touching_merges=True):
    """[1,3] and [3,5] merge when touching_merges (closed ends); stay apart otherwise."""
    if not spans:
        return []
    ordered = sorted(spans)
    out = []
    cur_lo, cur_hi = ordered[0]
    for lo, hi in ordered[1:]:
        overlaps = lo <= cur_hi if touching_merges else lo < cur_hi
        if overlaps:
            cur_hi = max(cur_hi, hi)
        else:
            out.append((cur_lo, cur_hi))
            cur_lo, cur_hi = lo, hi
    out.append((cur_lo, cur_hi))            # final flush: the last run is still open
    return out

def place_into_slots(values, n):
    """Domain contract: n ints, each in 1..n. Value v belongs at index v-1.
    Returns (slot, value) pairs left misplaced."""
    if len(values) != n or any(not 1 <= v <= n for v in values):
        raise ValueError(f"need {n} ints in 1..{n}")
    i = 0
    while i < n:
        j = values[i] - 1
        if values[i] != values[j]:          # guard: equal target means skip, never swap
            values[i], values[j] = values[j], values[i]
        else:
            i += 1
    return [(k + 1, v) for k, v in enumerate(values) if v != k + 1]

def place_unguarded(values, cap):
    i = steps = 0
    while i < len(values) and steps < cap:
        j = values[i] - 1
        values[i], values[j] = values[j], values[i]   # no duplicate guard
        steps += 1
        if values[i] == i + 1:
            i += 1
    return steps

spans = [(1, 3), (3, 5), (7, 8), (2, 2)]
print(merge_spans(spans), merge_spans(spans, touching_merges=False))
print(place_into_slots([3, 1, 3, 5, 2], 5))
print("no progress after", place_unguarded([3, 1, 3, 5, 2], 1000), "steps")
Output
[(1, 5), (7, 8)] [(1, 3), (3, 5), (7, 8)]
[(4, 3)]
no progress after 1000 steps

[(4, 3)] means slot 4 holds a stray 3. The unguarded variant, capped at 1,000 steps, never advances past index 0, where two equal 3s swap forever; the guard values[i] != values[j] is what ends the loop.

See it happen Cyclic placement with a duplicate

values (n=5)12335
  1. Index 0 holds 3, whose home is index 2, but index 2 already holds a 3, so the guard sees a duplicate and moves on.
  2. Index 1 holds 1, whose home is index 0, so they swap and 1 is now in its final slot.
  3. Index 3 holds 5, whose home is index 4, so 5 and 2 swap and the 5 is placed.
  4. The 2 now at index 3 belongs at index 1, so it swaps with the 3 there and 2 is placed.
  5. Slot 4 holds a stray 3 and slot 3 should hold 4, so the leftover reports a duplicate 3 and a missing 4.
Notice: every swap fixes one value for good, which is why the pass has at most n swaps.
Scenario A

In your world

The situation

A Jenkins job collapses a supplier's maintenance windows from three feeds into one blackout calendar, appending windows in file order and checking overlap only with the previous row.

What actually breaks

Feeds are unsorted, so a long early window is not adjacent to the short ones it contains. The calendar shows 211 blocks instead of 38 and prices are published during maintenance for 4 suppliers, with a green build.

What you'd do on Monday

Sort by start, merge with a signed-off rule for touching endpoints, flush the last group, and assert the output is sorted and non-overlapping.

Scenario B

Imagine you work at Hotstar

25M viewers, 150M watch intervals per match

The numbers

25M viewers × ~6 pause/resume intervals ≈ 150M intervals. A global sort costs 150M × log2(150M) ≈ 150M × 27.2 ≈ 4.1B comparisons. Grouping by viewer then sorting ~6 intervals each costs 25M × (6 × log2 6 ≈ 15.5) ≈ 390M.

What the Scenario-A answer does here

The Scenario A fix (sort all windows, then scan) is still correct. What breaks is cost and memory: sorting 150M tuples in one place needs roughly 150M × 100 B ≈ 15 GB and one huge shuffle.

What flips at this scale

Unique watch time needs overlaps only within the same viewer. Partition by viewer id, sort inside each partition (about 6 elements) and merge there. Player events arrive roughly ordered per session, so the sort is close to linear in practice.

The trade-off you'd defend

I would defend partition-then-merge over a global sort, trading a shuffle keyed by viewer for roughly 10x fewer comparisons and bounded memory per task.

Illustrative volumes and byte sizes for arithmetic; not Hotstar-published.

Gotchas

Forgetting the final flush

Symptom

The last merged block is missing; 38 expected, 37 returned.

Cause

A block is appended only when the next one does not overlap, so the last is never appended.

Fix

Append the current group after the loop.

Cyclic swap without a duplicate guard

Symptom

The job hangs at 100% CPU on a list containing two equal values.

Cause

Swapping values[i] with its target when both are equal changes nothing, so i never advances.

Fix

Skip when values[i] == values[target], and validate the 1..n range first.

Tricky questions

Can I merge intervals without sorting?
Most people say

A single pass in file order is enough since each span only needs its neighbour.

Actually

A long early span can overlap one far away in the file. Sort by start first or the scan is wrong.

Scenario question

You're handed a million maintenance windows from several feeds, some nested, some touching at an endpoint, and asked for a single blackout list.

Model answer

I'd first ask whether the end is inclusive, since that decides < or <=. Then I'd sort by start, scan with a running end using max, and flush at the end: O(n log n). The trade-off is the sort; if each feed is already sorted I'd do a k-way merge instead.

Interview corner

CommonWalk me through merging overlapping ranges.
“I'd sort by start, scan holding a current range, extend its end with max when the next start is at or before it, otherwise emit it and start a new one, and flush the last one.”
TrickWhat changes if touching ranges should not merge?
“I'd flip the comparison from less-or-equal to strictly less, after confirming the endpoint rule first, since it changes the output.”
TrickWhen is cyclic placement valid?
“I use it when I have n values each in 1..n so a value maps to an index. I'd also guard duplicates, otherwise two equal values swap forever.”

Memory hook

Sort the strips by left edge and glue as you go; return each parcel to its box.

If you remember only one thing:

Merge needs a sort and a final flush; cyclic placement needs a bounded domain and a duplicate guard.

Self-check

  1. Why take max of ends when merging?

    A contained span would otherwise shrink the current end.

  2. What decides < versus <=?

    Whether touching endpoints count as overlapping.

  3. What does the duplicate guard prevent?

    An endless swap of two equal values.

Prove it

Generate 100,000 random intervals with a seed. Run merge_spans and a brute-force union (mark minutes on a boolean array). Paste the output block count from each and an assertion that they are equal for both endpoint rules.