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
+vand−vat two boundaries is exactly differentiating a step function, and integrating it back recovers the original. That is whykrange updates over a timeline of lengthncostO(k + n)rather thanO(k · n); you never touch the interior of a range, only its two edges.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core 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(nums[start]) 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, because 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:
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, such as
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 beyond the output.
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(n + maxLoc) time, O(maxLoc) space, where n is the number of trips and maxLoc the largest coordinate (1000 in the lesson). For huge or sparse coordinates, sort the 2n events instead: O(n log n).
Missing Ranges
Report the gaps between a sorted array and a bounded interval [lower, upper]. The complement of run grouping: walk the values with a prev pointer, add a sentinel upper + 1 at the end (via itertools.chain, so the list is not copied), and emit [prev + 1, cur - 1] wherever cur - prev >= 2.
Pattern: gap walk. Target: O(n) time, O(1) extra space beyond the output.
6. Common pitfalls
- Using an inclusive end.
−vmust land atend, notend + 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.
- Dropping the leading or trailing gap in Missing Ranges. Start
prevatlower - 1and finish with the sentinelupper + 1, so both ends use the same test as the middle.
7. Key takeaways
- Record deltas, not values. Two point writes replace a whole range update.
- The end is exclusive. That single convention is what keeps adjacent ranges honest.
- One prefix-sum pass reconstructs the timeline, and the running total answers the question at every point.
- Close the final run after the loop.
- Bounded coordinates mean direct indexing; sparse or huge ones mean sorting the events instead.
- This is the counting cousin of merging. Merging asks which intervals overlap; sweeping asks how many.
- 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 → Missing Ranges.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson