Difference Array

What is a Difference Array?

A Difference Array is a technique that allows performing multiple range update operations efficiently. Instead of updating each element individually (O(n) per update), we can mark the start and end of each update and process them all at once.

Key Idea

Given array arr[0..n-1], create a difference array diff[0..n] where:

• diff[0] = arr[0]
• diff[i] = arr[i] - arr[i-1] for i > 0

To add val to range [l, r]:

• diff[l] += val
• diff[r+1] -= val

After all updates, reconstruct original array: arr[i] = arr[i-1] + diff[i]

Example

Initial array: arr = [0, 0, 0, 0, 0, 0, 0, 0]

Operation 1: Add 5 to range [2, 5]
Operation 2: Add 3 to range [4, 7]
Operation 3: Add 2 to range [0, 3]

Difference array approach:
1. diff[2] += 5, diff[6] -= 5
2. diff[4] += 3, diff[8] -= 3
3. diff[0] += 2, diff[4] -= 2

diff = [2, 0, 5, 0, 1, 0, -5, 0, -3]

Reconstruct:
arr[0] = 2
arr[1] = 2 + 0 = 2
arr[2] = 2 + 5 = 7
arr[3] = 7 + 0 = 7
arr[4] = 7 + 1 = 8
arr[5] = 8 + 0 = 8
arr[6] = 8 + (-5) = 3
arr[7] = 3 + 0 = 3

Final array: [2, 2, 7, 7, 8, 8, 3, 3]

Implementation

public class DifferenceArray {
    private int[] diff;
    private int n;
    
    public DifferenceArray(int size) {
        n = size;
        diff = new int[size + 1];
    }
    
    public DifferenceArray(int[] arr) {
        n = arr.length;
        diff = new int[n + 1];
        diff[0] = arr[0];
        for (int i = 1; i < n; i++) {
            diff[i] = arr[i] - arr[i - 1];
        }
    }
    
    // Add val to range [l, r] (0-indexed, inclusive)
    public void rangeUpdate(int l, int r, int val) {
        diff[l] += val;
        if (r + 1 <= n) {
            diff[r + 1] -= val;
        }
    }
    
    // Reconstruct the original array
    public int[] getArray() {
        int[] result = new int[n];
        result[0] = diff[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
    
    // Get prefix sum (sum of elements from 0 to i)
    public int getPrefixSum(int i) {
        int sum = 0;
        for (int j = 0; j <= i; j++) {
            sum += diff[j];
        }
        return sum;
    }
}

Time Complexity

• Range Update: O(1) per operation
• Reconstruct Array: O(n)
• Total for k updates: O(n + k)

Common Applications

1. Flight Range Bookings

// Book n flights from first to last, each booking[i] = [first, last, seats]
public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n + 1];
    
    for (int[] booking : bookings) {
        diff[booking[0] - 1] += booking[2]; // 1-indexed to 0-indexed
        diff[booking[1]] -= booking[2];
    }
    
    int[] result = new int[n];
    result[0] = diff[0];
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] + diff[i];
    }
    
    return result;
}

2. Car Pooling with Difference Array

public boolean carPooling(int[][] trips, int capacity) {
    int[] diff = new int[1001]; // Max location is 1000
    
    for (int[] trip : trips) {
        diff[trip[1]] += trip[0];  // Passengers get on
        diff[trip[2]] -= trip[0];  // Passengers get off
    }
    
    int currentPassengers = 0;
    for (int i = 0; i <= 1000; i++) {
        currentPassengers += diff[i];
        if (currentPassengers > capacity) {
            return false;
        }
    }
    
    return true;
}

3. Range Addition with Final Query

// After all updates, answer multiple queries
public int[] getModifiedArray(int length, int[][] updates) {
    int[] diff = new int[length + 1];
    
    for (int[] update : updates) {
        diff[update[0]] += update[2];
        diff[update[1] + 1] -= update[2];
    }
    
    int[] result = new int[length];
    result[0] = diff[0];
    for (int i = 1; i < length; i++) {
        result[i] = result[i - 1] + diff[i];
    }
    
    return result;
}

4. Difference Array with Prefix Sum

// 2D Difference Array for matrix updates
public void updateMatrix(int[][] matrix, int r1, int c1, int r2, int c2, int val) {
    int m = matrix.length, n = matrix[0].length;
    int[][] diff = new int[m + 1][n + 1];
    
    diff[r1][c1] += val;
    diff[r1][c2 + 1] -= val;
    diff[r2 + 1][c1] -= val;
    diff[r2 + 1][c2 + 1] += val;
    
    // Reconstruct using 2D prefix sums
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
            matrix[i][j] += diff[i + 1][j + 1];
        }
    }
}