Pattern #8
Difference Array
Important interview questions, thinking patterns, range update logic, and rules for solving difference array problems in Go.
Must Solve
10 core questions โ solve these first.
- 1.Range Additiondiff[L]+=val, diff[R+1]-=valmedium
- 2.Corporate Flight BookingsFlight seats range updatemedium
- 3.Car PoolingCapacity start/stop stopsmedium
- 4.Maximum Population YearBirth +1, Death -1easy
- 5.Shifting Letters IIShift range net countmedium
- 6.Minimum Number of K Consecutive Bit FlipsGreedy + Difference statehard
- 7.Zero Array Transformation IRange decrements checkmedium
- 8.Zero Array Transformation IIBinary search + Diff arraymedium
- 9.Check if Grid can be Cut into SectionsInterval merge / Line sweepmedium
- 10.Describe the PaintingColor mix at boundariesmedium
Also Important
7 more questions worth practicing.
- 11.Range Addition IIMin boundary overlapeasy
- 12.My Calendar problemsTreemap / Sweep linemedium
- 13.Meeting Rooms / Overlapping IntervalsStart +1, End -1easy
- 14.Amount of New Area Painted Each DaySegment tree / Diff arrayhard
- 15.Number of Flowers in Full BloomBloom start +1, End+1 -1hard
- 16.Range Coverage ProblemsCoverage boundariesmedium
- 17.Sweep Line + Difference Array problemsCoordinate compressionmedium
How to Think
- Many updates on ranges?Difference Array
- Add +V from index L to R?diff[L] += V, diff[R+1] -= V
- Need many interval additions?start += val, end + 1 -= val
- Need final values after all updates?Difference Array + Prefix Sum
Go Thinking & Reference
Basic Range Update & Rebuild
// 1. Mark range updates in O(1)
diff := make([]int, n+1)
diff[l] += value
if r+1 < n {
diff[r+1] -= value
}
// 2. Rebuild final values in O(n)
current := 0
for i := 0; i < n; i++ {
current += diff[i]
arr[i] += current
}๐ M updates + 1 rebuild: O(M + N) time | O(N) space
Main Idea & Example
Original: [0, 0, 0, 0, 0]
Update: Add +5 from index 1 to 3
Difference: [0, +5, 0, 0, -5]
Prefix sum: [0, 5, 5, 5, 0]
Result: [0, 5, 5, 5, 0] โ
L ---------------- R
โ โ
+X stop after R (R+1)
diff[L] += X
diff[R+1] -= X
Prefix Sum โ Final Array๐ก Golden Rule: "Mark where the change starts and where it stops โ don't update every element."
Difference Array vs Prefix Sum
| Technique | Primary Purpose | Update Cost | Query Cost |
|---|---|---|---|
| Prefix Sum | Many range QUERIES | O(n) per update | O(1) per query |
| Difference Array | Many range UPDATES | O(1) per update | O(n) rebuild at end |
Interview Rules
- 1. Many range updates? โ Difference Array
- 2. Add same value to L..R? โ Difference Array
- 3. Start/end events? โ Difference Array
- 4. Overlapping intervals? โ Think Difference / Sweep Line
- 5. Need final result after all updates? โ Prefix once at the end
- 6. Start effect โ
diff[L] += x - 7. Stop effect โ
diff[R+1] -= x - 8. Many range queries instead? โ Prefix Sum
Small Rules
- Rule 1: Difference array makes single range update O(1) instead of O(len).
- Rule 2: M updates + 1 rebuild is O(M + N) instead of O(M ร N).
- Rule 3: L starts the effect, R + 1 stops the effect.
- Rule 4: Check bounds! If
R + 1 == n, do not access outside array. - Rule 5: Best when many updates happen first, and final values are read later.
Production Thinking
Pricing / Promotions โ Discount on product range 1000..5000 in O(1)
Traffic / Capacity โ +10 passengers at stop 2, -10 after stop 6
Booking Systems โ Room occupied 10:00..12:00 โ +1 at start, -1 at end
Server Load โ +3 workers min 10..20, +5 workers min 15..25
Remember This
Range update โ Difference Array
Start at L โ +X
Stop after R (R+1) โ -X
Final values โ Prefix Sum
Many updates โ O(1) each
Many range queries โ Prefix Sum instead๐ก Golden Rule: "Mark where the change starts and where it stops โ don't update every element."