Difference Arrays: O(1) Range Updates for Interview Problems

Some interview problems hand you a list of operations like "add 5 to every element from index 2 to 7" and then ask for the final array. Applying each update directly costs O(n) per operation. A difference array makes each update O(1).

The idea

Store d[i] = a[i] - a[i-1]. Adding v to the range [l, r] only changes two entries: d[l] += v and d[r+1] -= v. After all updates, one prefix sum over d rebuilds the array.

def apply_ranges(n, ops):
    d = [0] * (n + 1)
    for l, r, v in ops:
        d[l] += v
        d[r + 1] -= v
    out, run = [], 0
    for i in range(n):
        run += d[i]
        out.append(run)
    return out

Total cost: O(n + q) instead of O(n * q).

Problems where it is the intended answer

• Corporate flight bookings / range addition: the direct application above.
• Car pooling: add passengers at pickup, subtract at drop-off, then check the running total never exceeds capacity.
• Meeting rooms (count overlap): +1 at start, -1 at end; the maximum prefix sum is the number of rooms needed. With large coordinates, use a sorted map instead of an array.
• Minimum flips / shifting letters: track how many pending range operations affect the current index as you sweep.

Extensions worth mentioning

• 2D difference arrays: a rectangle update touches four corners; rebuild with a 2D prefix sum.
• Coordinate compression when indices go up to 10^9 but there are only a few thousand events.
• When updates and queries interleave, a difference array no longer works on its own; move to a Fenwick tree over the difference array (range update, point query) or a lazy segment tree.

Interview tip

Say the pattern out loud: "updates are offline and only the final state matters, so I'll record boundaries and sweep once." Then mention the off-by-one at r+1, which is the bug interviewers watch for.

Disclosure: I help build Linkjob AI coding interview assistant. These notes are independent practice material.