Range Addition

Problem (restated)

Array of length length starts at 0. updates[i] = [start, end, inc] adds inc to inclusive range. Return final array.

Intuition

+inc at start, -inc at end+1; prefix sum materializes the array in O(n).

Approaches

export function getModifiedArray(length: number, updates: number[][]): number[] {
  const diff = Array(length + 1).fill(0);
  for (const u of updates) {
    diff[u[0]!] += u[2]!;
    diff[u[1]! + 1] -= u[2]!;
  }
  const res = Array(length).fill(0);
  let cur = 0;
  for (let i = 0; i < length; i++) {
    cur += diff[i]!;
    res[i] = cur;
  }
  return res;
}

export function getModifiedArray(length: number, updates: number[][]): number[] {
  const diff = Array(length + 1).fill(0);
  for (const u of updates) {
    diff[u[0]!] += u[2]!;
    diff[u[1]! + 1] -= u[2]!;
  }
  const res = Array(length).fill(0);
  let cur = 0;
  for (let i = 0; i < length; i++) {
    cur += diff[i]!;
    res[i] = cur;
  }
  return res;
}

Template connection

Difference array batch range updates.

Reflection

• Writing each update straight into the array costs updates * n. You do diff[l] += v and diff[r + 1] -= v, then one prefix. Why is that enough?
• When r + 1 == n, where does the subtraction go? If the array is only length n, does the last cell disappear?
• Overlapping updates add up in the prefix. With no updates, is the answer n zeros?