Range Addition

Range Addition

What is this problem about?

The Range Addition problem gives you an array of zeros and a list of updates: each update adds a value to all positions in a range [l, r]. Compute the final array after all updates. This coding problem is the canonical application of the difference array technique. The array and prefix sum interview pattern is directly demonstrated.

Why is this asked in interviews?

Salesforce, Amazon, and Google ask this because the difference array technique — applying range updates in O(1) each, then computing the final array in O(n) — is a fundamental optimization that appears across many interview problems. It tests knowledge beyond standard prefix sums.

Algorithmic pattern used

Difference array. Initialize diff[0..n] = 0. For each update (l, r, val): diff[l] += val; diff[r+1] -= val. Compute prefix sum of diff: result[i] = sum(diff[0..i]). This gives the final array.

Example explanation

n=5, updates=[[1,3,2],[2,4,3],[0,2,-2]]. diff = [0,0,0,0,0,0] (size n+1).

• [1,3,2]: diff[1]+=2, diff[4]-=2. diff=[0,2,0,0,-2,0].
• [2,4,3]: diff[2]+=3, diff[5]-=3. diff=[0,2,3,0,-2,-3].
• [0,2,-2]: diff[0]+=-2, diff[3]+=2. diff=[-2,2,3,2,-2,-3]. Prefix sum: -2, 0, 3, 5, 3, 0. Result (first 5): [-2,0,3,5,3].

Common mistakes candidates make

• Not extending diff array to n+1 (need diff[r+1] even when r=n-1).
• Not computing prefix sum after all updates.
• Confusing prefix sum direction.
• Off-by-one in the range endpoints (l and r are inclusive).

Interview preparation tip

The difference array is the range-update counterpart to prefix sum (which handles range queries). Difference array → O(1) range update + O(n) build. Prefix sum → O(n) build + O(1) range query. Together they're called a "point-update, range-query" structure. Practice applying difference arrays to: "paint fences," "meeting rooms III," "bus stop passengers." This is a must-know interview pattern.