Range Addition

Range Addition asks you to apply a pile of range updates to an array and report only the final result. The trick that makes it fast — the difference array — collapses each range update into just two writes, and is one of the most reusable array patterns in interviews.

The slow way first

The literal approach: do exactly what the prompt describes. For each update, loop from start to end and add inc to every cell along the way. That is correct, but with many wide updates it is O(updates × length) — a single update can repaint the whole array, and there may be thousands of them.

The question to ask: each update is a flat block of +inc. Do I truly need to write every cell inside that block? What if I only noted where the change starts and where it stops, and rebuilt the array a single time at the end?

The idea: record only the edges of each change

Keep a helper array called diff, the difference array, of length length + 1. Rather than painting a whole range, mark only its two boundaries:

• diff[start] += inc — the increment turns on here.
• diff[end + 1] -= inc — the increment turns off one step past the end.

Once every update is recorded, sweep diff from left to right with a running total (a prefix sum). At each index the running total equals the sum of every increment that has turned on and not yet turned off — which is precisely the final value at that index.

The extra slot at index length earns its keep: when end is the last index, end + 1 would step off the array. Making diff one cell longer gives that subtraction a harmless home, and the spare slot is simply never read back.

Walk through it

Step through the animation. For each update the +inc pointer lands on diff[start] and the -inc pointer lands on diff[end + 1] — only those two cells move. After all three updates, diff = [2, 4, -2, -1, -4, 1]. Then the sum pointer sweeps left to right, folding each cell into a running total, and the answer cells lock in green as [2, 6, 4, 3, -1] emerges.

Pseudocode

diff = array of (length + 1) zeros
for each update [start, end, inc]:
    diff[start]   += inc          # increment turns on
    diff[end + 1] -= inc          # increment turns off
running = 0
for each index i from 0 to length - 1:
    running += diff[i]            # prefix sum
    res[i] = running
return res

The Python solution

def get_modified_array(length, updates):
    diff = [0] * (length + 1)
    for start, end, inc in updates:
        end_plus = end + 1
        diff[start] += inc
        diff[end_plus] -= inc
    res, running = [0] * length, 0
    for i in range(length):
        running += diff[i]
        res[i] = running
    return res

• diff has length + 1 slots so the diff[end_plus] write is always in range.
• For each update we do two O(1) writes — never a loop across the range.
• diff[start] += inc turns the increment on; diff[end_plus] -= inc turns it off one step past the end.
• The second loop is a prefix sum: running accumulates every active increment, so running at index i is the final value there.
• We only ever read diff[0] through diff[length - 1], so the helper slot at index length is harmlessly ignored.

Complexity

We trade O(n) extra space (the diff array) for a large speed win when updates are plentiful: each one becomes O(1) instead of O(n), and a single O(n) pass reconstructs the answer.

When this pattern shows up

Practice