</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Sweep-line idea: record only where values change

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 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:

Car pooling delta array and capacity sweep

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. −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.
  • Dropping the leading or trailing gap in Missing Ranges. Start prev at lower - 1 and finish with the sentinel upper + 1, so both ends use the same test as the middle.

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 → 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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.