Definition of Difference Arrays#

For an array nums, define the difference array:

1
diff[0] = nums[0]
2
diff[i] = nums[i] - nums[i-1]        (i ≥ 1)

In other words, diff[i] records the difference between two adjacent elements — the value itself doesn’t matter; how much the value “changed” is what matters.

Conversely, accumulating diff from the start (doing one prefix sum) restores nums:

1
nums[i] = diff[0] + diff[1] + ... + diff[i]

diff and nums have an inverse relationship between prefix sums and difference arrays: nums is the prefix sum of diff, and diff is the difference array of nums. One handles “accumulation,” the other handles “change.”

Why Range Addition Only Touches Two Endpoints#

Adding delta to every element in the range [left, right] is equivalent to performing two point updates on diff:

1
diff[left]     += delta        /* Starting from left, raise everything by delta */
2
diff[right + 1] -= delta       /* Starting from right+1, undo the raise */

The monotone-looking diff might be hard to grasp, but it becomes intuitive when drawn out. Taking nums = [1, 2, 3, 4, 5] and adding 2 to [1, 3] as an example:

1
nums:   1   2   3   4   5
2
diff:   1   1   1   1   1        ← original difference
3

4
Add 2 at left=1:
5
diff:   1   3   1   1   1
6
Subtract 2 at right+1=4:
7
diff:   1   3   1   1  -1        ← only two positions changed
8

9
Restore by prefix sum:
10
nums:   1   4   5   6   5        ← indices 1..3 all +2, the rest unchanged  ✓

The principle in one sentence: a difference array records the “rate of change.” Adding a step at left raises all prefix sums from left onward; then subtracting the same step at right+1 restores things after right. Between the two steps is exactly [left, right].

The Three-Stage Template#

Difference array problems always have three stages, regardless of which problem, the structure is fixed:

1
① Marking: for each operation [left, right, delta]:
2
            diff[left]     += delta
3
            diff[right+1]  -= delta
4
② Restore: running = 0
5
        for i in 0..n-1:  running += diff[i];  ans[i] = running
6
③ Check/Retrieve: for those requiring a global check (such as whether carpooling is overloaded), check while scanning in ②

The reason diff has length n + 1 is precisely for the right + 1 in stage ① — when right == n - 1, it falls at index n, and the extra slot catches it exactly, so you never need to write if (right + 1 < n). This slot doesn’t participate in the accumulation in stage ②; it’s purely a “trash bin.”

Complexity: Why It’s Fast#

A single range addition goes from “traversing the entire range” to “modifying two numbers,” at the cost of queries being deferred until a final restoration. This is the pricing of difference arrays for speed: it sells “batch modifications” and charges “deferred queries.”

Problem Description#

Given an all-zero array of length length, and several operations updates[i] = [startIdx, endIdx, inc]. Each operation means adding inc to every element in the index range [startIdx, endIdx] (inclusive of both ends). Return the array after all operations have been executed.

Example:

1
length = 5
2
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
3

4
result = [-2, 0, 3, 5, 3]

Constraints: 0 <= length <= 10^5, 0 <= updates.length <= 10^4.

Approach: Initially all zeros, so we can even skip building the table#

In this problem the initial array is all 0s, so diff is also initially all 0s — the first step of building the difference array is skipped entirely. We just need to allocate an all-zero array of length length + 1, mark each operation as two points, and finally restore via prefix sums.

This is the cleanest kind of difference-array problem: no initial values → no build phase → three segments become two.

1
#include <stdlib.h>
2

3
int *getModifiedArray(int length, int **updates, int updatesSize,
4
                      int *updatesColSize, int *returnSize) {
5
    int *diff = (int *)calloc(length + 1, sizeof(int));   /* allocate one extra slot to cover end+1 */
6
    for (int i = 0; i < updatesSize; i++) {
7
        int start = updates[i][0], end = updates[i][1], inc = updates[i][2];
8
        diff[start]     += inc;         /* raise the left endpoint of the range */
9
        diff[end + 1]   -= inc;         /* undo after the right endpoint */
10
    }
11

12
    int *res = (int *)malloc(length * sizeof(int));
13
    int running = 0;
14
    for (int i = 0; i < length; i++) {
15
        running    += diff[i];          /* restore the prefix sum */
16
        res[i]      = running;
17
    }
18
    free(diff);
19
    *returnSize = length;
20
    return res;
21
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
7
        vector<int> diff(length + 1, 0);          // allocate one extra slot to cover end + 1
8
        for (auto& u : updates) {
9
            diff[u[0]]     += u[2];               // raise the left endpoint of the range
10
            diff[u[1] + 1] -= u[2];               // undo after the right endpoint
11
        }
12

13
        vector<int> res(length);
14
        int running = 0;
15
        for (int i = 0; i < length; i++)
16
            res[i] = (running += diff[i]);        // restore the prefix sum
17
        return res;
18
    }
19
};

1
function getModifiedArray(length, updates) {
2
  const diff = new Array(length + 1).fill(0); // allocate one extra slot to cover end + 1
3
  for (const [start, end, inc] of updates) {
4
    diff[start] += inc; // raise the left endpoint of the range
5
    diff[end + 1] -= inc; // undo after the right endpoint
6
  }
7

8
  const res = new Array(length).fill(0);
9
  let running = 0;
10
  for (let i = 0; i < length; i++) {
11
    running += diff[i]; // restore the prefix sum
12
    res[i] = running;
13
  }
14
  return res;
15
}

Complexity#

Common Pitfalls#

1. diff is only allocated length. Then when end == length - 1, writing diff[end + 1] as diff[length] will go out of bounds. Allocating one extra slot is the easiest fix for this problem, cleaner than checking end + 1 < length every time.
2. diff[end + 1] was written as diff[end]. This shifts the “undo” one position earlier, causing the element at index end to undo itself as well, which is equivalent to only adding the value to [start, end-1] — the result is off by one at the boundary.
3. Merging the “marking phase” and the “restoration phase”. Some people think “update the answer array immediately after each operation”, but that degenerates into an O(n·m) brute force, wasting the difference array. You must first mark all m operations as points, then restore all at once at the end.

Problem Description#

There are n flights, numbered from 1 to n. Given booking records bookings[i] = [first_i, last_i, seats_i], representing seats_i seats booked from the first_i-th to the last_i-th flight (inclusive). Return an array answer of length n, where answer[i] is the total number of seats booked on the i + 1-th flight.

Example:

1
bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5
2
result = [10, 55, 45, 25, 25]

Constraints: 1 <= n <= 2 · 10^4, the numbering range of bookings[i] is 1 <= first <= last <= n.

Approach: This problem is just 370, only the coordinate system has changed#

Compared to Example One, 1109 has two “translations” to make, both at the index level:

1. 1-indexed → 0-indexed: The flight numbers in the problem are 1..n, while array indices are 0..n-1. The left endpoint first of the interval should be written as diff[first - 1].
2. The semantics of the right endpoint: This is a closed interval [first, last], but according to the difference array formula, the cancellation point should fall at last + 1 (1-indexed). Converting to a 0-indexed array, last + 1 happens to equal last—so what’s written in the code is diff[last] -= seats, which looks like forgetting +1, but it’s actually correct.

Let’s verify point 2: [1, 2, 10] means flights 1 and 2 each get 10 added. Using diff[0] += 10 and diff[2] -= 10, when reconstructing, diff[0] and diff[1] receive 10, and cancellation starts from diff[2]—hitting indices 0 and 1, which are exactly flights 1 and 2. ✓

1
bookings = [[1,2,10], [2,3,20], [2,5,25]], n = 5
2

3
Marking points (0-indexed, diff length n+1 = 6):
4
  index:   0     1     2     3     4     5
5
  [1,2]   +10         -10
6
  [2,3]         +20         -20
7
  [2,5]         +25                     -25   ← the undo point falls at index 5 (trash slot)
8
  ───────────────────────────────────────────
9
  diff:    10    45   -10   -20     0   -25
10

11
Take the prefix sum only over indices 0..4:
12
  10 → 55 → 45 → 25 → 25
13
Result = [10, 55, 45, 25, 25]   ✓

Note that last = 5 of the last booking equals n, and the cancellation point diff[5] falls exactly on the extra slot (the trash bin position)—it doesn’t participate in the output, it only ensures that “no one after flight 5 gets anything.” This also confirms why diff needs to be allocated with size n + 1.

1
#include <stdlib.h>
2

3
int *corpFlightBookings(int **bookings, int bookingsSize, int *bookingsColSize,
4
                        int n, int *returnSize) {
5
    int *diff = (int *)calloc(n + 1, sizeof(int));   /* allocate one extra slot to cover last */
6
    for (int i = 0; i < bookingsSize; i++) {
7
        int first = bookings[i][0], last = bookings[i][1], seats = bookings[i][2];
8
        diff[first - 1] += seats;    /* 1-indexed → 0-indexed */
9
        diff[last]      -= seats;    /* after +1 on the closed-interval right endpoint, it lands exactly on last, right-open */
10
    }
11

12
    int *res = (int *)malloc(n * sizeof(int));
13
    int running = 0;
14
    for (int i = 0; i < n; i++) {
15
        running += diff[i];
16
        res[i]   = running;
17
    }
18
    free(diff);
19
    *returnSize = n;
20
    return res;
21
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
7
        vector<int> diff(n + 1, 0);              // allocate one extra slot to cover last
8
        for (auto& b : bookings) {
9
            diff[b[0] - 1] += b[2];              // 1-indexed → 0-indexed
10
            diff[b[1]]     -= b[2];              // after +1 on the closed-interval right endpoint, it lands exactly on b[1]
11
        }
12

13
        vector<int> res(n);
14
        int running = 0;
15
        for (int i = 0; i < n; i++)
16
            res[i] = (running += diff[i]);
17
        return res;
18
    }
19
};

1
function corpFlightBookings(bookings, n) {
2
  const diff = new Array(n + 1).fill(0); // allocate one extra slot to cover last
3
  for (const [first, last, seats] of bookings) {
4
    diff[first - 1] += seats; // 1-indexed → 0-indexed
5
    diff[last] -= seats; // after +1 on the closed-interval right endpoint, it lands exactly on last
6
  }
7

8
  const res = new Array(n).fill(0);
9
  let running = 0;
10
  for (let i = 0; i < n; i++) {
11
    running += diff[i];
12
    res[i] = running;
13
  }
14
  return res;
15
}

Complexity#

Common Pitfalls#

1. Forgetting the 1-indexed conversion. The first and last in the problem are flight numbers (starting from 1). Using them directly as array indices shifts the entire result right by one and drops one at the end. The left endpoint must be written as first - 1.
2. Adding one to last on your own. This is the most counterintuitive point in this problem: the “cancellation point” in the difference array formula is right + 1, but that’s last + 1 under 1-indexed; converting to a 0-indexed array, index last + 1 subtracts 1 again, and the net result is diff[last]. So in the code, last does not carry +1. Mnemonic: The input is already a 1-based “right-open position”—use it directly as a 0-based cancellation point.
3. Allocating only n slots for diff. The maximum value of last is n, and diff[n] needs to exist—allocating one extra slot (n + 1) is safe; otherwise, if the last booking covers flight n, you’ll write out of bounds.
4. Writing the reconstruction range as n + 1. The extra slot is a trash bin, the output has only n numbers, and the loop upper bound is n.

Problem Description#

A car has a capacity of capacity and can only drive in one direction. Given trips trips[i] = [numPassengers_i, from_i, to_i], representing picking up numPassengers_i people at stop from_i and dropping them off at stop to_i. Determine whether this car can handle all trips in one go (i.e., the number of people in the car never exceeds capacity at any moment).

Example:

1
trips = [[2,1,5], [3,3,7]], capacity = 4      → false
2
   // Between stations 3 and 5, there are 2 + 3 = 5 people on the vehicle at the same time > 4
3

4
trips = [[2,1,5], [3,3,7]], capacity = 5      → true

Constraints: 1 <= trips.length <= 1000, 0 <= from_i < to_i <= 1000.

Approach: Range Addition, but What’s Being “Added” Is the Number of People#

Treat each trip [from, to) as an interval and add numPassengers people to it — range addition again! Except this time, what we want is not “the exact number of people at each stop,” but rather “whether the peak during the process exceeds capacity.”

So the second part of the template (restoration) needs to be changed to accumulate and check simultaneously: running is “the number of people in the car after each stop,” and as soon as it exceeds capacity, immediately return false.

Note that the interval is right-open [from, to): passengers get off at stop to, so stop to is not counted toward this trip’s occupancy. Written with difference arrays, this is diff[from] += num, diff[to] -= num — the cancellation point falls on to itself, with no extra plus one, because to is exactly the first position that is “not included.”

1
trips = [[2,1,5], [3,3,7]], capacity = 4
2

3
diff (stops 0..1000):
4
  diff[1] += 2 ; diff[5] -= 2
5
  diff[3] += 3 ; diff[7] -= 3
6

7
Accumulate stop by stop (only look at nonzero positions):
8
  stop  0   1   2   3   4   5   6   7
9
  diff  0  +2   0  +3   0  -2   0  -3
10
  onboard  0   2   2   5   5   3   3   0
11
                └─── peak 5 > 4, false ───┘

1
#include <stdbool.h>
2

3
bool carPooling(int **trips, int tripsSize, int *tripsColSize, int capacity) {
4
    int diff[1001] = {0};                /* station coordinates ≤ 1000, a static array is enough */
5
    for (int i = 0; i < tripsSize; i++) {
6
        int num = trips[i][0], from = trips[i][1], to = trips[i][2];
7
        diff[from] += num;               /* board at station from */
8
        diff[to]   -= num;               /* alight at station to: the range is right-open [from, to) */
9
    }
10

11
    int current = 0;
12
    for (int i = 0; i <= 1000; i++) {
13
        current += diff[i];              /* number of people on board after this station */
14
        if (current > capacity) return false;
15
    }
16
    return true;
17
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    bool carPooling(vector<vector<int>>& trips, int capacity) {
7
        vector<int> diff(1001, 0);       // station coordinates ≤ 1000
8
        for (auto& t : trips) {
9
            diff[t[1]] += t[0];          // board at station from
10
            diff[t[2]] -= t[0];          // alight at station to: the range is [from, to)
11
        }
12

13
        int current = 0;
14
        for (int change : diff)
15
            if ((current += change) > capacity) return false;
16
        return true;
17
    }
18
};

1
function carPooling(trips, capacity) {
2
  const diff = new Array(1001).fill(0); // station coordinates ≤ 1000
3
  for (const [num, from, to] of trips) {
4
    diff[from] += num; // board at station from
5
    diff[to] -= num; // alight at station to: the range is [from, to)
6
  }
7

8
  let current = 0;
9
  for (const change of diff) {
10
    current += change; // number of people on board after this station
11
    if (current > capacity) return false;
12
  }
13
  return true;
14
}

Complexity#

Common Pitfalls#

1. Writing stop to as diff[to + 1] -= num. This causes passengers to not get off at stop to, occupying one extra stop, which may be misjudged as overcapacity. to is the “drop-off” position, equivalent to the endpoint of a right-open interval, with no plus one.
2. Reversing the interval endpoints. Some people are used to writing closed intervals, so they write diff[from] += num; diff[to + 1] -= num — if the problem statement really says “occupying a seat at stop to,” then that’s correct; but this problem explicitly states that to is drop-off, so it’s right-open. First confirm the problem’s definition of endpoints, then decide whether to add one.
3. Timing of the overcapacity check. It must be checked immediately after accumulating at each stop — this problem asks for “any moment during the process,” not “the final total.” If it exceeds capacity halfway through accumulation, you can exit early with return false.
4. No sorting, no simulating people at each stop. A common mistake is sorting by from and then simulating pickups and drop-offs. The difference array naturally gives “the net change at each stop” — just scan through without moving, and sorting is unnecessary overhead.
5. Coordinate range. to can be as large as 1000, so diff needs to be at least 1001 long; writing new Array(1000) will cause an out-of-bounds at the maximum stop.

6.1 2D Difference: Adding the Same Value to an Entire Submatrix#

One dimension is “range add, mark two endpoints”; two dimensions is “submatrix add, mark four corners.” To add v to an entire rectangular region (r1, c1) ~ (r2, c2) of a matrix (all four corners inclusive):

1
diff[r1][c1]         += v      /* Starting from the top-left corner, raise the entire bottom-right region */
2
diff[r1][c2 + 1]     -= v      /* Undo: after the right boundary */
3
diff[r2 + 1][c1]     -= v      /* Undo: after the bottom boundary */
4
diff[r2 + 1][c2 + 1] += v      /* Add back: the bottom-right corner was subtracted twice, add it back */

Does this look familiar? The sign order at the four corners, + − − +, is the same set as the inclusion-exclusion formula for 2D prefix sum queries. This is no coincidence—2D prefix sum and 2D difference are inverse operations of each other:

1
Marking points (using differences to record changes)  ── 2D prefix sum ──▶  Reconstruct the actual matrix

To restore, perform a 2D prefix sum on diff (accumulate in place):

1
for i in 0..m-1:
2
    for j in 0..n-1:
3
        if i > 0:      diff[i][j] += diff[i-1][j]        /* above */
4
        if j > 0:      diff[i][j] += diff[i][j-1]        /* left */
5
        if i>0 && j>0: diff[i][j] -= diff[i-1][j-1]      /* top-left was added twice */
6
        /* at this point diff[i][j] is the value of the final matrix at (i, j) */

A typical problem is LeetCode 2536. Increment Submatrices by One (add 1 to the submatrix of each query). C++ skeleton:

1
vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
2
    vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));   // allocate one extra ring
3
    for (auto& q : queries) {
4
        int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
5
        diff[r1][c1]++;
6
        diff[r1][c2 + 1]--;
7
        diff[r2 + 1][c1]--;
8
        diff[r2 + 1][c2 + 1]++;
9
    }
10
    for (int i = 0; i < n; i++)
11
        for (int j = 0; j < n; j++) {                         // in-place 2D prefix sum
12
            if (i) diff[i][j] += diff[i - 1][j];
13
            if (j) diff[i][j] += diff[i][j - 1];
14
            if (i && j) diff[i][j] -= diff[i - 1][j - 1];
15
        }
16
    diff.resize(n);                                            // discard that extra ring
17
    for (auto& row : diff) row.resize(n);
18
    return diff;
19
}

Just like in one dimension: “allocating one extra ring” is to catch +1, and you simply discard it at the end.

6.2 Tree Difference: Adding to an Entire Path#

One dimension is a “segment,” two dimensions is a “rectangle,” and on a tree it’s a “path”: add x to every vertex on the simple path from u → v in the tree. The approach is to move the difference onto the tree’s subtree prefix sum—mark four points, then do one final DFS to compute subtree sums and restore:

To restore, compute subtree sums via post-order traversal: val[u] += Σ val[child], in O(n) time. The essence is still that old saying—“record changes where they happen”: a path add = the superposition of two “upward adds,” which cancel each other out at the LCA.

6.3 Generalization: The Sweep-Line Idea#

The essence of difference arrays is not an array trick, but a more general idea:

Don’t record the value at every position—only record the positions where “the value changes,” then sweep from left to right and accumulate them.

Problem 1094 Car Pooling is a live example—we never simulated “someone boards at some stop, someone alights at some stop” from start to finish; we only recorded the net change in passenger count at each stop, and a single sweep gives us the number of passengers on board at any moment. The same idea under a different name is:

• Sweep-line algorithm: split intervals into two events, “enter +1, leave −1,” sort them, and sweep once (compare with area union, interval coverage counting).
• Event-timeline statistics: in booking systems and logging systems, record increments/decrements only at “start/end” moments, rather than maintaining state second by second.

1D difference = the sweep line specialized to “intervals on the number line.” Once you recognize this layer, difference arrays are no longer about “memorizing formulas,” but about “keeping accounts at the points of change.”

6.4 Selection and Pitfalls: When Not to Use Difference Arrays#

Difference arrays are a specialized tool for “batch range modifications.” As soon as the requirement involves “modify while querying,” they’re no longer sufficient:

An easily confused name: Difference Constraints have nothing to do with the difference arrays in this article—they are a class of “systems of inequalities of the form x_j − x_i ≤ c,” solved using shortest paths / SPFA. Both have “difference” in the name, but one is an array trick and the other is a graph-theoretic model—don’t mix them up.