Pattern 8 of 27

Difference Array

Record only where each range update starts and stops, then one running sum applies every update at once.

Cost: O(n + k) time, O(n) space
Problems: 6

When to reach for it

Many updates add a value to a whole range.
You only need the final array, or one scan after every update is in.
Updating each range element by element would be too slow.

How it works

A difference array stores changes rather than values. Adding v to indices l through r becomes two edits: plus v at l, and minus v just after r. Once every update is recorded, a running sum over the difference array rebuilds the real values, so k updates over n positions cost O(n + k) instead of O(n × k). The same idea applied to events sorted by time is the sweep line, which is how Car Pooling and most range-coverage problems are solved.

The template

Written for Corporate Flight Bookings

def corp_flight_bookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats      # range starts here
        diff[last] -= seats           # and stops after here
    out, running = [], 0
    for i in range(n):
        running += diff[i]
        out.append(running)
    return out

Open in the editor Trace it line by line

Six problems, in learning order

1.Range AdditionLeetCode 370PremiumThe textbook version: k range additions and one final running sum.Not in the curated 370 yet.Medium
2.Car PoolingLeetCode 1094Add passengers at pickup, remove them at drop-off, and check capacity during the sweep.Not in the curated 370 yet.Medium
3.Corporate Flight BookingsLeetCode 1109Bookings are range additions over 1-based flight numbers.Not in the curated 370 yet.Medium
4.Check if All the Integers in a Range Are CoveredLeetCode 1893Mark the covered ranges, then check the queried range holds no zero.Not in the curated 370 yet.Easy
5.Describe the PaintingLeetCode 1943Sweep the change points and emit a segment whenever the running colour sum changes.Not in the curated 370 yet.Medium
6.Shifting Letters IILeetCode 2381Range shifts on letters: sum the differences, then shift each letter modulo 26.Not in the curated 370 yet.Medium

What usually goes wrong

Writing the minus at r instead of r + 1, which ends every range one step early.
Mixing 1-based ranges from the prompt with 0-based arrays.
Forgetting that the array needs one extra slot for the write at r + 1.