← All patternsDifference Array · template
Pattern · Pointers & Windows
Difference Array
Apply many "add v to range [l, r]" updates in O(1) each by marking +v at l and -v at r + 1, then take a prefix sum once.
Time O(n + updates) · Space O(n)
Taught in Module 5: Prefix Sum
Think of it like this
Marking a calendar: write "+3 guests" on the day a group arrives and "-3" the day after they leave; a running total gives the headcount every day.
Clues that point here
- → Many range updates, then read the final array once
- → Bookings, flights or seats over ranges of days
- → "Add value to every element between i and j"
Not this pattern when
- ✕ You need to read values between updates (use a Fenwick or segment tree)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int[] diff = new int[n + 1];
for (int[] u : updates) { // u = {l, r, value}
diff[u[0]] += u[2];
diff[u[1] + 1] -= u[2];
}
int[] result = new int[n];
int running = 0;
for (int i = 0; i < n; i++) { running += diff[i]; result[i] = running; }
return result;Common versions
- Corporate flight bookings
- Car pooling
- Range addition
- 2D difference arrays