The difference array is the inverse of prefix sum. While prefix sum enables O(1) range queries, difference array enables O(1) range updates.
You've mastered prefix sum for reading ranges. Now imagine the opposite problem: you need to update multiple ranges efficiently. Instead of updating every element in a range (O(n) per update), difference arrays let you update in O(1).
This pattern appears in range update problems, event scheduling, and resource allocation. It's a favorite in interviews because it tests your ability to think inversely.
This guide will teach you what difference arrays are, how they relate to prefix sum, complete templates, and when to use this pattern.
Use difference array when:
Template:
# Initialize difference array
diff = [0] * (n + 1)
# Apply updates in O(1) each
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct final array with prefix sum
result = []
current = 0
for i in range(n):
current += diff[i]
result.append(current)Time: O(n + k) where k = number of updates
Space: O(n)
Prefix sum: Given an array, compute cumulative sums
Difference array: Given cumulative sums, recover the original array
The relationship:
If prefix[i] = sum of nums[0..i-1]
Then nums[i] = prefix[i+1] - prefix[i]
This "difference" is why it's called a difference array!Key insight: To add val to range [start, end]:
diff[start] by valdiff[end+1] by valWhen we apply prefix sum to reconstruct, this creates a "plateau" from start to end.
Visual example:
Want to add 3 to range [1, 3] in array of size 5
Difference array changes:
diff[1] += 3
diff[4] -= 3
diff = [0, 3, 0, 0, -3, 0]
Apply prefix sum:
result[0] = 0
result[1] = 0 + 3 = 3
result[2] = 3 + 0 = 3
result[3] = 3 + 0 = 3
result[4] = 3 + (-3) = 0
Result: [0, 3, 3, 3, 0] ✓
Added 3 to indices 1, 2, 3!Think of it as creating a step function:
diff[start] += val creates an upward stepdiff[end+1] -= val creates a downward stepdef range_addition(length: int, updates: List[List[int]]) -> List[int]:
"""
Apply multiple range updates efficiently.
Args:
length: Size of the array
updates: List of [start, end, val] updates
Returns:
Final array after all updates
Time: O(n + k) where k = number of updates
Space: O(n)
"""
# Initialize difference array (size n+1 for safety)
diff = [0] * (length + 1)
# Apply all updates to difference array: O(k)
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct final array with prefix sum: O(n)
result = []
current = 0
for i in range(length):
current += diff[i]
result.append(current)
return result
# Test
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
print(range_addition(5, updates))
# [-2, 0, 3, 5, 3]function rangeAddition(length, updates) {
const diff = new Array(length + 1).fill(0);
// Apply updates
for (const [start, end, val] of updates) {
diff[start] += val;
diff[end + 1] -= val;
}
// Reconstruct with prefix sum
const result = [];
let current = 0;
for (let i = 0; i < length; i++) {
current += diff[i];
result.push(current);
}
return result;
}
// Test
const updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]];
console.log(rangeAddition(5, updates));
// [-2, 0, 3, 5, 3]public int[] rangeAddition(int length, int[][] updates) {
int[] diff = new int[length + 1];
// Apply updates
for (int[] update : updates) {
int start = update[0], end = update[1], val = update[2];
diff[start] += val;
diff[end + 1] -= val;
}
// Reconstruct with prefix sum
int[] result = new int[length];
int current = 0;
for (int i = 0; i < length; i++) {
current += diff[i];
result[i] = current;
}
return result;
}You have an array of length n, initially all zeros. You have k update operations, each represented as [startIdx, endIdx, inc]. Apply all updates and return the final array.
Example:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]
Explanation:
Initial: [0, 0, 0, 0, 0]
Update 1: [0, 2, 2, 2, 0] (add 2 to range [1,3])
Update 2: [0, 2, 5, 5, 3] (add 3 to range [2,4])
Update 3: [-2, 0, 3, 5, 3] (add -2 to range [0,2])def getModifiedArray(length: int, updates: List[List[int]]) -> List[int]:
"""
LeetCode #370: Range Addition
Time: O(n + k), Space: O(n)
"""
diff = [0] * (length + 1)
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
result = []
current = 0
for i in range(length):
current += diff[i]
result.append(current)
return resultTrace for updates = [[1,3,2],[2,4,3],[0,2,-2]]:
After update [1,3,2]:
diff = [0, 2, 0, 0, -2, 0]
After update [2,4,3]:
diff = [0, 2, 3, 0, -2, -3]
After update [0,2,-2]:
diff = [-2, 2, 3, -2, -2, -3]
Reconstruct:
i=0: current = 0 + (-2) = -2
i=1: current = -2 + 2 = 0
i=2: current = 0 + 3 = 3
i=3: current = 3 + 0 = 3... wait, should be 5
Let me recalculate:
After [1,3,2]: diff = [0, 2, 0, 0, -2, 0]
After [2,4,3]: diff = [0, 2, 3, 0, -2-3, 0] = [0, 2, 3, 0, -5, 0]
Wait, end+1 for [2,4,3] is 5, not 4
Let me redo:
Update [1,3,2]: diff[1]+=2, diff[4]-=2
diff = [0, 2, 0, 0, -2, 0]
Update [2,4,3]: diff[2]+=3, diff[5]-=3
diff = [0, 2, 3, 0, -2, -3]
Update [0,2,-2]: diff[0]+=-2, diff[3]-=(-2)
diff = [-2, 2, 3, 2, -2, -3]
Reconstruct:
i=0: current = 0 + (-2) = -2
i=1: current = -2 + 2 = 0
i=2: current = 0 + 3 = 3
i=3: current = 3 + 2 = 5
i=4: current = 5 + (-2) = 3
Result: [-2, 0, 3, 5, 3] ✓There are n flights, and bookings[i] = [first, last, seats] means book seats seats for flights first through last (1-indexed). Return an array where answer[i] is the total seats booked for flight i.
Example:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight 1: 10 (from booking 1)
Flight 2: 10 + 20 + 25 = 55
Flight 3: 20 + 25 = 45
Flight 4: 25
Flight 5: 25def corpFlightBookings(bookings: List[List[int]], n: int) -> List[int]:
"""
LeetCode #1109: Corporate Flight Bookings
Time: O(n + k), Space: O(n)
"""
diff = [0] * (n + 1)
for first, last, seats in bookings:
# Convert to 0-indexed
diff[first - 1] += seats
diff[last] -= seats
result = []
current = 0
for i in range(n):
current += diff[i]
result.append(current)
return result
# Test
bookings = [[1,2,10],[2,3,20],[2,5,25]]
print(corpFlightBookings(bookings, 5))
# [10, 55, 45, 25, 25]Each booking is a range update. Difference array handles all updates in O(1) each.
You're driving a car with capacity seats. Given trips = [[numPassengers, from, to]], determine if you can pick up and drop off all passengers.
Example:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation:
At location 3, we have 2 + 3 = 5 passengers, exceeding capacity 4def carPooling(trips: List[List[int]], capacity: int) -> bool:
"""
LeetCode #1094: Car Pooling
Time: O(n + max_location), Space: O(max_location)
"""
# Find max location
max_loc = max(to for _, _, to in trips)
# Use difference array for passenger changes
diff = [0] * (max_loc + 1)
for passengers, from_loc, to_loc in trips:
diff[from_loc] += passengers # Pick up
diff[to_loc] -= passengers # Drop off
# Check if capacity is ever exceeded
current = 0
for i in range(max_loc + 1):
current += diff[i]
if current > capacity:
return False
return True
# Test
trips = [[2,1,5],[3,3,7]]
print(carPooling(trips, 4)) # False
print(carPooling(trips, 5)) # TruePassengers getting on/off are range updates. We track cumulative passengers at each location and check if capacity is exceeded.
| Aspect | Prefix Sum | Difference Array |
|---|---|---|
| Purpose | Range queries | Range updates |
| Operation | Read sum of range | Add to range |
| Query time | O(1) | N/A |
| Update time | O(n) rebuild | O(1) |
| Reconstruction | Build once | Apply at end |
| Relationship | Forward (cumulative) | Inverse (differences) |
Use Prefix Sum when:
Use Difference Array when:
Use Both when:
❌ Wrong:
# Apply updates but forget to reconstruct
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
return diff # WRONG! This is the difference array, not the result✅ Correct:
# Apply updates
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct with prefix sum
result = []
current = 0
for i in range(n):
current += diff[i]
result.append(current)
return result # ✓ CorrectSee guide: Difference Array Mistakes
❌ Wrong:
# Forgetting +1 on end
diff[start] += val
diff[end] -= val # Should be end+1Result: The value at index end is not updated.
✅ Correct:
diff[start] += val
diff[end + 1] -= val # ✓ Correct❌ Wrong:
diff = [0] * n # Too small!
diff[end + 1] -= val # May be out of bounds✅ Correct:
diff = [0] * (n + 1) # Extra space for end+1❌ Wrong:
# Applying prefix sum before all updates
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct here? NO!✅ Correct:
# Apply ALL updates first
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Then reconstruct once
current = 0
for i in range(n):
current += diff[i]
result.append(current)Time Complexity:
Space Complexity: O(n) for difference array
Comparison:
| Approach | Time | Space |
|---|---|---|
| Naive (update each element) | O(k × n) | O(1) |
| Difference array | O(n + k) | O(n) |
| Speedup | ~k times faster | Uses O(n) space |
Break-even: When k ≥ 2, difference array is already faster.
Master difference arrays with these problems:
Beginner:
Intermediate:
3. Car Pooling (#1094) - Capacity checking
4. Brightest Position on Street (#2021) - Event-based updates
Advanced:
5. My Calendar III (#732) - Overlapping events
6. Amount of New Area Painted Each Day (#2158) - Complex range updates
Q: When should I use difference array vs segment tree?
A: Use difference array when:
Use segment tree when:
Q: Can difference array handle multiplicative updates?
A: No, it only works for additive updates (add/subtract). For multiplication, use other techniques.
Q: Why is it called a "difference" array?
A: Because it stores the differences between consecutive elements. When you apply prefix sum, you recover the original values.
Q: Do I always need size n+1?
A: Yes, to safely handle diff[end+1] without bounds checking.
Q: Can I use difference array for 2D matrices?
A: Yes! The concept extends to 2D, but it's more complex. You'd apply the same logic in both dimensions.
Difference arrays are the inverse of prefix sum, enabling O(1) range updates.
Key principles:
The template:
# Apply updates
diff = [0] * (n + 1)
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Reconstruct
result = []
current = 0
for i in range(n):
current += diff[i]
result.append(current)When to use:
Master this pattern, and you'll solve range update problems efficiently. For more, see the complete prefix sum guide, 1D template, and difference array mistakes.
Next time you see "multiple range updates," reach for difference arrays.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free