Difference Array Complete Guide - Master O(1) Range Updates

Overview

The Difference Array is a powerful technique for handling multiple range updates efficiently. It’s the inverse operation of prefix sum and is critical for interview problems involving:

• Range addition/subtraction
• Timeline simulations
• Booking systems
• Interval operations

Why Interviewers Love It: Tests your ability to optimize from O(n×m) brute force to O(n+m) using clever preprocessing.

---

🔗 Relationship with Prefix Sum

Difference array and prefix sum are inverse operations!

The Beautiful Symmetry

Original Array ←────────→ Difference Array
               Difference       Prefix Sum

Forward (Building Difference Array):

arr[i] → diff[i] = arr[i] - arr[i-1]

Backward (Reconstructing Array):

diff[i] → arr[i] = arr[i-1] + diff[i]  (Prefix Sum!)

Visual Comparison

Array:      [3,  5,  2,  7,  4]
Index:       0   1   2   3   4

Difference: [3,  2, -3,  5, -3]
            ↑   ↑   ↑   ↑   ↑
           3  5-3 2-5 7-2 4-7

Key Insight 💡

Operation	Prefix Sum	Difference Array
Building	Add cumulative sum	Compute differences
Purpose	Fast range queries	Fast range updates
Update	O(n)	O(1) ✓
Query	O(1) ✓	O(n)
Reconstruction	N/A	Needs prefix sum!

The Connection:

• Prefix sum accumulates changes
• Difference array records changes
• They are mathematical inverses!

---

Building the Difference Array

💡 Algorithm

1. Create array of size n + 1 (extra space for boundary)
2. Set diff[0] = arr[0] (base case)
3. For each index i, compute diff[i] = arr[i] - arr[i-1]

🎮 Interactive Visualization

Watch how the difference array captures changes between consecutive elements.

💻 Template Code

JavaScriptJavaPython

Loading...

✅ Key Points

• Size: Difference array has n + 1 elements (extra for boundary)
• First Element: diff[0] = arr[0] (no previous element)
• Difference: diff[i] stores the change from arr[i-1] to arr[i]
• Time: O(n) to build
• Purpose: Records incremental changes

---

O(1) Range Update ⚡

This is the killer feature of difference arrays!

💡 The Magic Formula

To add value to range [left, right]:

diff[left] += value;      // Mark START of range
diff[right + 1] -= value; // Mark END of range

Why Does This Work?

When we reconstruct using prefix sum:
  
  Position left:       Gets +value from diff[left]
  Positions (left+1) to right:  Inherit +value (prefix sum carries it forward)
  Position (right+1):  Gets -value, canceling the effect
  Positions after:     No effect (canceled out)

🎮 Interactive Visualization

See how a range update only modifies TWO positions!

💻 Template Code

JavaScriptJavaPython

Loading...

📊 Detailed Example

Initial array: [3, 5, 2, 7, 4]
Initial diff:  [3, 2, -3, 5, -3, 0]

Operation: Add 10 to range [1, 3]
────────────────────────────────────

Step 1: diff[1] += 10
   diff = [3, 12, -3, 5, -3, 0]
         ─────↑

Step 2: diff[4] -= 10
   diff = [3, 12, -3, 5, -13, 0]
         ─────────────────↑

Reconstruct (apply prefix sum):
   [3, 15, 12, 17, 4]
       ↑   ↑   ↑
    Added 10 to these positions! ✓

Complexity Analysis

Method	Time per Update	Total for m Updates
Brute Force	O(n)	O(n × m)
Difference Array	O(1) ✓	O(m) ✓

For 1000 updates on array of size 10000:

• Brute force: 10,000,000 operations
• Difference array: 1,000 operations + reconstruction

10,000× faster! 🚀

---

Reconstructing the Array

After all updates, we need to get the final array. This is where prefix sum comes in!

💡 Algorithm

Apply prefix sum to the difference array:

arr[0] = diff[0]
arr[i] = arr[i-1] + diff[i]  // Prefix sum!

🎮 Interactive Visualization

Watch how prefix sum converts the difference array back to the original array.

💻 Template Code

JavaScriptJavaPython

Loading...

The Full Workflow

Step 1: Build difference array
   Array:  [3, 5, 2, 7, 4]
     ↓
   Diff:   [3, 2, -3, 5, -3, 0]

Step 2: Apply updates (O(1) each)
   Update [1,3] +10: diff[1]+=10, diff[4]-=10
   Update [0,2] -5:  diff[0]-=5, diff[3]+=5
     ↓
   Diff:   [-2, 12, -3, 10, -13, 0]

Step 3: Reconstruct (prefix sum)
     ↓
   Result: [-2, 10, 7, 17, 4]

---

Interview Problems

Problem 1: Range Addition (LC 370) 🔒

Note: This is a LeetCode Premium problem. You need a subscription to submit.

Problem: Given an array of length n initialized with zeros, and a list of range update operations, return the final array.

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]
After [1,3,2]:    [0, 2, 2, 2, 0]
After [2,4,3]:    [0, 2, 5, 5, 3]
After [0,2,-2]:   [-2, 0, 3, 5, 3]

Key Insight: Perfect use case for difference array!

JavaScriptJavaPython

Loading...

Complexity: O(n + m) time, O(n) space where m = number of updates

Interview Tip: This is the fundamental pattern — master it first!

---

Problem 2: Corporate Flight Bookings (LC 1109)

Problem: Process flight bookings where each booking reserves seats on a range of flights.

Input: bookings = [[1,2,10], [2,3,20], [2,5,25]], n = 5
Output: [10, 55, 45, 25, 25]

Explanation:
Flight 1: 10 seats
Flight 2: 10 + 20 + 25 = 55 seats
Flight 3: 20 + 25 = 45 seats
Flight 4: 25 seats
Flight 5: 25 seats

Key Insight: Each booking is a range update. Perfect for difference array!

JavaScriptJavaPython

Loading...

Complexity: O(n + m) time, O(n) space

Interview Tip: Watch out for 1-indexed input! Convert to 0-indexed.

---

Problem 3: Car Pooling (LC 1094)

Problem: Determine if a car with given capacity can complete all trips without exceeding capacity.

Input: trips = [[2,1,5], [3,3,7]], capacity = 4
Output: false

Explanation:
At location 3: 2 + 3 = 5 passengers > 4 capacity

Key Insight: Use difference array as a timeline to track passenger changes!

JavaScriptJavaPython

Loading...

Complexity: O(max_location) time, O(max_location) space

Why This Works:

Location:  0  1  2  3  4  5  6  7  8
Diff:      0 +2  0 +3  0 -2  0 -3  0
                 ↑     ↑
            Pick up  Drop off

After prefix sum (simulate timeline):
Passengers: 0  2  2  5  5  3  3  0  0
                    ↑
                Exceeds capacity!

---

Problem 4: Separate Squares I (LC 3453)

Problem: Find the minimum y-coordinate of a horizontal line that divides squares such that the total area above equals the total area below.

Input: squares = [[0,0,2],[1,1,1]]
Output: 1.16667

Explanation:
At y = 7/6 (≈ 1.16667):
- Area below: 7/6 × 2 + 1/6 = 2.5
- Area above: 5/6 × 2 + 5/6 = 2.5

Key Insight: Use difference array with sweep line algorithm to track horizontal edge lengths at each y-coordinate!

Problem Analysis

This problem combines multiple advanced techniques:

1. Difference Array: Track changes in horizontal edge lengths
2. Sweep Line: Scan from bottom to top calculating cumulative area
3. Binary Search: Find exact split point within a segment

Understanding the Approach

The key insight is that we don’t care about the x-coordinate at all! We only need to track:

• Which y-coordinates have edge changes (squares start or end)
• The total horizontal edge length at each y level
• Cumulative area as we sweep upward

Why diff[y] not diff[y+1]?

For a square [x, y, l]:

• It covers the vertical range [y, y+l) (left-closed, right-open interval)
• At y: horizontal edge length increases by l
• At y+l: horizontal edge length decreases by l

This is exactly like Car Pooling!

Square [0,0,2]: covers y ∈ [0, 2)

Height:  0    1    2    3
Diff:   +2    0   -2    0
        ↑         ↑
     Start      End

After prefix sum (horizontal edge length at each height):
EdgeLen: 0 → 2 → 2 → 0 → 0

Algorithm Steps

Step 1: Build Difference Array

For each square [x, y, l]:
  diff[y] += l      // Horizontal edge starts
  diff[y+l] -= l    // Horizontal edge ends

Step 2: Sweep Line from Bottom to Top

Sort all y-coordinates with changes
For each y:
  1. Calculate area in [preY, y) using current edge length
  2. Check if we've reached half of total area
  3. If yes, binary search within [preY, y) for exact split
  4. Update edge length for next segment

Step 3: Binary Search for Exact Split

If area * 2 >= totArea:
  // We've passed the halfway point
  // Need to go back by: (area * 2 - totArea) / 2
  // Height to go back: excess_area / edge_length
  return y - (area * 2 - totArea) / (sumL * 2.0)

JavaScriptJavaPython

Loading...

Complexity: O(n log n) time (sorting), O(n) space

Detailed Example Walkthrough

Input: squares = [[0,0,2],[1,1,1]]

Step 1: Build Difference Array

Square [0,0,2]: diff[0] += 2, diff[2] -= 2
Square [1,1,1]: diff[1] += 1, diff[2] -= 1

Result:
diff = {
  0: +2,   // Two edges start (only red square)
  1: +1,   // One edge starts (blue square)
  2: -3    // Both red and one blue edge end
}

Step 2: Sweep and Calculate

Total Area = 2×2 + 1×1 = 5
Target = 5/2 = 2.5

y=0: area = 0 + 0×(0-0) = 0,    sumL = 0+2 = 2
     0 < 2.5, continue
     
y=1: area = 0 + 2×(1-0) = 2,    sumL = 2+1 = 3
     2 < 2.5, continue
     
y=2: area = 2 + 3×(2-1) = 5,    sumL = 3-3 = 0
     5 ≥ 2.5, FOUND!
     
     Exact position:
     return 2 - (5×2 - 5) / (3×2.0)
          = 2 - 5/6
          = 7/6
          ≈ 1.16667

Visualization:

y-axis
  3 |
  2 |-----------|  ← Edge ends here
    |    RED    |
  1 |-----+----|  ← Blue starts, red continues
    |     |BLUE|
  0 |-----|----|  ← Red starts
    0     1    2  x-axis

Horizontal edge lengths at each y:
y ∈ [0,1): length = 2 (red only)
y ∈ [1,2): length = 3 (red + blue overlap region)
y ≥ 2:     length = 0

Area calculation:
[0,1): 2 × 1 = 2
[1,y]: 3 × (y-1)

Total below y: 2 + 3(y-1) = 3y - 1
Set equal to half: 3y - 1 = 2.5
                   3y = 3.5
                   y = 7/6 ≈ 1.16667

Why This Works

1. Difference Array: Efficiently tracks where horizontal edges appear/disappear
2. Sorted Scan: Processes y-coordinates in order, maintaining cumulative area
3. Rectangle Area Formula: area = width × height
   • Width = sum of horizontal edge lengths (sumL)
   • Height = vertical distance (y - preY)
4. Linear Interpolation: Once we know which segment contains the split, we calculate exact position

Key Observations

1. X-coordinate doesn’t matter — only horizontal projection matters
2. Overlapping squares count multiple times — that’s why we sum edge lengths
3. Left-closed, right-open interval [y, y+l) — same as Car Pooling semantics
4. TreeMap/Sorted keys ensure we process y-coordinates in order

Interview Tips

• Don’t overthink x-coordinates: The problem is purely about y-axis projection
• Watch out for overlap: Edge lengths add up, not replace
• Precision: Use double for the final answer (binary search gives fractional result)
• Edge case: All squares start at y=0? Still works with sweep line!

---

When to Use Which: Prefix Sum vs Difference Array

Decision Matrix

Scenario	Use	Reason
Many range queries, few updates	Prefix Sum	O(1) queries
Many range updates, few queries	Difference Array	O(1) updates
Need both frequent queries and updates	Segment Tree	O(log n) both
Static array (no updates)	Prefix Sum	Simple & fast
Only building once, querying once	Brute force	Simpler code

Problem Type Recognition

Use Prefix Sum When:

• “Find sum of range [L, R]”
• “Count subarrays with sum = k”
• “Range query” problems
• Array is read-heavy

Use Difference Array When:

• “Add value to range [L, R]”
• “Multiple booking/reservation operations”
• “Timeline simulation”
• Array is write-heavy

Complexity Comparison

Operation	Brute Force	Prefix Sum	Difference Array
Build	-	O(n)	O(n)
Range Query	O(n)	O(1) ✓	O(n)
Range Update	O(n)	O(n)	O(1) ✓
Final Query	O(1)	O(1)	O(n)

The Inverse Relationship

Difference Array → Prefix Sum → Original Array
    (build)         (reconstruct)

Original Array → Difference Array → Final Array
   (changes)          (apply)       (compute)

---

Common Pitfalls

1. Forgetting the Boundary Element

❌ Wrong:

const diff = new Array(n).fill(0);  // Too small!
diff[right + 1] -= value;  // May go out of bounds!

✅ Correct:

const diff = new Array(n + 1).fill(0);  // Extra space for boundary
diff[right + 1] -= value;  // Safe!

Why: We need diff[right + 1] to mark where the range ends.

---

2. Forgetting to Reconstruct

❌ Wrong:

// Apply updates to diff[]
rangeUpdate(diff, 0, 2, 5);
return diff;  // Wrong! This is difference array, not result!

✅ Correct:

// Apply updates to diff[]
rangeUpdate(diff, 0, 2, 5);
return reconstructArray(diff, n);  // Reconstruct first!

---

3. Index Off-by-One Errors

❌ Wrong (when input is 1-indexed):

// bookings[i] = [first, last, seats] (1-indexed)
diff[first] += seats;  // Wrong! Should be first-1

✅ Correct:

// Convert to 0-indexed
diff[first - 1] += seats;
diff[last] -= seats;  // last is already correct (exclusive end)

---

4. Not Understanding Prefix Sum Connection

❌ Wrong Mental Model: “Difference array is a separate technique.”

✅ Correct Understanding: “Difference array requires prefix sum for reconstruction. They are inverse operations!“

---

5. Using When Not Needed

Don’t Use Difference Array If:

• Only one range update → Just use loop
• Need frequent queries between updates → Use Segment Tree
• Array is very small (< 100) → Brute force is fine

---

Summary

🔑 Core Concepts

Difference Array = Records changes between consecutive elements
Prefix Sum = Accumulates those changes back to original array

They are inverse operations!

📋 Quick Reference

Operation	Time	Space
Build difference array	O(n)	O(n)
Range update	O(1) ✓	-
Reconstruct array	O(n)	-
Total for m updates	O(n + m)	O(n)

🎯 Pattern Recognition

Use Difference Array When You See:

• “Add value to range [L, R]”
• “Multiple booking operations”
• “Timeline simulation”
• “Range update” problems
• Many updates, few final queries

Template Pattern:

1. Build difference array (O(n))
2. Apply all updates (O(1) each)
3. Reconstruct using prefix sum (O(n))

💡 Key Takeaways

1. Inverse of Prefix Sum: They undo each other
2. O(1) Updates: Mark start and end, that’s it!
3. Reconstruction Needed: Always apply prefix sum at the end
4. Boundary Element: Array size is n + 1
5. Perfect for Ranges: When you have many range operations

🚀 Interview Pro Tips

1. Recognize the Pattern: “Multiple range updates” → Think difference array
2. Explain the Math: Show how prefix sum reconstructs the array
3. Draw It Out: Visualize the difference and reconstruction
4. Consider Trade-offs: Explain why this beats brute force
5. Watch Boundaries: Don’t forget the n + 1 size!

🎯 Interview Template: When you see “range update”:

1. Can I use difference array? (Many updates, few queries?)
2. Build diff array: diff[i] = arr[i] - arr[i-1]
3. Update: diff[L] += val; diff[R+1] -= val
4. Reconstruct: Apply prefix sum

📚 Related Topics

• Prefix Sum: The inverse operation — master both!
• Segment Tree: When you need both fast updates AND queries
• Binary Indexed Tree (Fenwick Tree): Alternative for range operations
• Sweep Line Algorithm: Similar timeline-based thinking

The Beautiful Symmetry

Array → [Difference] → Diff Array
Diff Array → [Prefix Sum] → Array

They complete each other! 🔄

Master difference arrays and prefix sums together — they’re two sides of the same coin! 🚀