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 Addition
diff[L]+=val, diff[R+1]-=valmedium
2.Corporate Flight Bookings
Flight seats range updatemedium
3.Car Pooling
Capacity start/stop stopsmedium
4.Maximum Population Year
Birth +1, Death -1easy
5.Shifting Letters II
Shift range net countmedium
6.Minimum Number of K Consecutive Bit Flips
Greedy + Difference statehard
7.Zero Array Transformation I
Range decrements checkmedium
8.Zero Array Transformation II
Binary search + Diff arraymedium
9.Check if Grid can be Cut into Sections
Interval merge / Line sweepmedium
10.Describe the Painting
Color mix at boundariesmedium

Also Important

7 more questions worth practicing.

11.Range Addition II
Min boundary overlapeasy
12.My Calendar problems
Treemap / Sweep linemedium
13.Meeting Rooms / Overlapping Intervals
Start +1, End -1easy
14.Amount of New Area Painted Each Day
Segment tree / Diff arrayhard
15.Number of Flowers in Full Bloom
Bloom start +1, End+1 -1hard
16.Range Coverage Problems
Coverage boundariesmedium
17.Sweep Line + Difference Array problems
Coordinate 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] ✅

Visual Memory Rule

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."