Sweep and Ranges

What is this?

A bus route has forty stops and a hundred bookings, each covering a stretch of the journey. To check the bus never exceeds capacity you could add every booking's passengers to every stop it covers — thousands of updates. Or you could note, at each stop, only the change: passengers boarding, passengers leaving. Walk the route once adding up the changes, and the running total at every stop is the load.

That is the difference-array idea, and it is the same instinct as grouping consecutive numbers into ranges: the interesting information lives at the boundaries.

💡 Fun fact: the difference array is the discrete derivative, and the prefix-sum pass that reconstructs the timeline is the discrete integral. Recording +v and −v at two boundaries is exactly differentiating a step function, and integrating it back recovers the original. That is why k range updates over a timeline of length n cost O(k + n) rather than O(k · n) — you never touch the interior of a range, only its two edges.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: never touch the inside of a range. Record what changes at its two edges, make one ordered pass, and let the accumulation reconstruct everything in between.

1. The difference array

delta = [0] * (max_position + 1)
for passengers, start, end in trips:
    delta[start] += passengers
    delta[end]   -= passengers          # end is EXCLUSIVE — they get off here

load = 0
for stop in range(len(delta)):
    load += delta[stop]
    if load > capacity:
        return False
return True

The exclusive end is the whole correctness argument. A passenger travelling [2, 5) is aboard at stops 2, 3 and 4 but not at 5 — so writing −v at 5 rather than 6 is what stops back-to-back trips being double-counted. Getting this wrong produces answers that are right for isolated ranges and wrong the moment two ranges touch.

2. Run grouping

ranges, i, n = [], 0, len(nums)
while i < n:
    start = i
    while i + 1 < n and nums[i + 1] == nums[i] + 1:
        i += 1                                   # extend while consecutive
    ranges.append(str(start_val) if start == i else f"{nums[start]}->{nums[i]}")
    i += 1

Two details cause most bugs here. The single-element case formats differently ("4", not "4->4"), and the final run must be emitted after the loop ends — there is no "next value" to trigger its closure.

3. A 30-second worked example (car pooling)

Trips (2 passengers, 1→5), (3 passengers, 3→7), capacity 4:

delta:  index  0  1  2  3  4  5  6  7
               0 +2  0 +3  0 -2  0 -3

sweep:
  stop 1 → load 2   ✓
  stop 3 → load 5   ✗ exceeds capacity 4  → return False

The two trips overlap on stops 3 and 4, and the running total exposes that at stop 3 without ever enumerating which trips are aboard. With capacity 5 the same sweep would return True.

4. Where you'll actually meet this

• Capacity checks. Vehicle occupancy, room bookings and connection pools — anything where claims overlap in time.
• Monitoring and alerting. Counting concurrent requests over a window without storing each one.
• Genomics. Coverage depth along a reference sequence is a difference array over read alignments.
• Billing and metering. Aggregating overlapping usage windows into a per-interval total.
• Data compression and display. Collapsing consecutive identifiers into ranges — 1-5, 8, 11-14 — in page selectors and log summaries.

5. Problems in this chapter

▶ Summary Ranges

Compress a sorted array into range strings. One pass holding the start of the current run, closing it when the chain breaks, and flushing the final run afterwards.
Pattern: run grouping. Target: O(n) time, O(1) extra space.

▶ Car Pooling

Decide whether a vehicle's capacity is ever exceeded. Difference array over the route, then a prefix-sum sweep checking the running load.
Pattern: difference array + prefix sum. Target: O(k + n) time, O(n) space.

6. Common pitfalls 🚫

• Using an inclusive end. −v must land at end, not end + 1, or touching trips double-count.
• Forgetting the last run. Nothing triggers its closure inside the loop, so it must be emitted afterwards.
• Formatting single elements as a range. "4", not "4->4".
• Sizing the delta array too small. It needs one slot past the maximum coordinate.
• Sorting trips before sweeping. Unnecessary when coordinates are bounded — index directly. Sorting only helps when coordinates are sparse or huge.
• Checking capacity after the sweep. The limit must be tested at every stop, since the peak may occur mid-route.
• Assuming the input is sorted in Summary Ranges. It is stated as sorted; if it were not, that assumption would silently produce wrong ranges.

7. Key takeaways

1. Record deltas, not values. Two point writes replace a whole range update.
2. The end is exclusive. That single convention is what keeps adjacent ranges honest.
3. One prefix-sum pass reconstructs the timeline, and the running total answers the question at every point.
4. Close the final run after the loop.
5. Bounded coordinates mean direct indexing; sparse or huge ones mean sorting the events instead.
6. This is the counting cousin of merging. Merging asks which intervals overlap; sweeping asks how many.
7. Why interviewers like it: the naive per-position update is the obvious answer and is quadratic. Reaching for boundaries instead is a small, transferable insight they can test in ten minutes.

Order: Summary Ranges → Car Pooling.