Difference Array Technique

The Prefix Sum Technique is mainly used in scenarios where the original array is not modified, but frequent queries of the cumulative sum of a certain range are needed. The core code is as follows:

class PrefixSum {
    // prefix sum array
    private int[] preSum;

    // input an array to construct the prefix sum
    public PrefixSum(int[] nums) {
        // preSum[0] = 0, convenient for calculating cumulative sum
        preSum = new int[nums.length + 1];
        // calculate the cumulative sum of nums
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    // query the cumulative sum of the closed interval [left, right]
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

class PrefixSum {
private:
    vector<int> prefix;

public:
    // prefix sum array
    PrefixSum(vector<int>& nums) {
        prefix = vector<int>(nums.size() + 1);
        // calculate the cumulative sum of nums
        for (int i = 1; i < nums.size() + 1; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

    // query the cumulative sum of the closed interval [i, j]
    int query(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
};

class PrefixSum:
    # Prefix sum array
    def __init__(self, nums: List[int]):
        self.prefix = [0] * (len(nums) + 1)
        # Calculate the cumulative sum of nums
        for i in range(1, len(self.prefix)):
            self.prefix[i] = self.prefix[i - 1] + nums[i - 1]
    
    # Query the cumulative sum of the closed interval [i, j]
    def query(self, i: int, j: int) -> int:
        return self.prefix[j + 1] - self.prefix[i]

type PrefixSum struct {
    // prefix sum array
    prefix []int
}

// input an array, construct the prefix sum
func Constructor(nums []int) *PrefixSum {
    prefix := make([]int, len(nums)+1)
    // calculate the cumulative sum of nums
    for i := 1; i < len(prefix); i++ {
        prefix[i] = prefix[i-1] + nums[i-1]
    }
    return &PrefixSum{prefix}
}

// query the cumulative sum of the closed interval [i, j]
func (ps *PrefixSum) Query(i, j int) int {
    return ps.prefix[j+1] - ps.prefix[i]
}

class PrefixSum {
    constructor(nums) {
        // prefix sum array
        this.prefix = new Array(nums.length + 1);
        // calculate the cumulative sum of nums
        for (let i = 1; i < this.prefix.length; i++) {
            this.prefix[i] = this.prefix[i - 1] + nums[i - 1];
        }
    }

    // query the cumulative sum of the closed interval [i, j]
    query(i, j) {
        return this.prefix[j + 1] - this.prefix[i];
    }
}

preSum[i] represents the cumulative sum of all elements in nums[0..i-1]. If we want to find the cumulative sum of the interval nums[i..j], we can simply calculate preSum[j+1] - preSum[i] without needing to traverse the entire interval.

This article introduces an algorithm technique very similar to the prefix sum concept, called the "difference array". The main use case for the difference array is when you frequently need to increment or decrement elements in a specific interval of the original array.

For example, given an array nums, you might be asked to increment all elements in the interval nums[2..6] by 1, then decrement all elements in nums[3..9] by 3, then increment all elements in nums[0..4] by 2, and so on.

After a series of operations, you are asked to determine the final values in the nums array.

The conventional approach is straightforward: if you need to add val to the interval nums[i..j], you simply use a for loop to add val to each element. However, this approach has a time complexity of O(N), which can be very inefficient given the frequent modifications to nums.

This is where the difference array technique comes in. Similar to how we construct the preSum array with the prefix sum technique, we first construct a diff difference array for the nums array. diff[i] is the difference between nums[i] and nums[i-1]:

int[] diff = new int[nums.length];
// construct the difference array
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

int diff[nums.size()];
// construct the difference array
diff[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
    diff[i] = nums[i] - nums[i - 1];
}

# Here is the corrected code with the appropriate translations:

diff = [0] * len(nums)
# Construct the difference array
diff[0] = nums[0]
for i in range(1, len(nums)):
    diff[i] = nums[i] - nums[i - 1]

// Construct the difference array
diff := make([]int, len(nums))
diff[0] = nums[0]
for i := 1; i < len(nums); i++ {
    diff[i] = nums[i] - nums[i-1]
}

var diff = new Array(nums.length);
// construct the difference array
diff[0] = nums[0];
for (var i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

Using this diff difference array, you can reconstruct the original array nums. The code logic is as follows:

int[] res = new int[diff.length];
// construct the result array based on the difference array
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

int res[diff.size()];
// construct the result array based on the difference array
res[0] = diff[0];
for (int i = 1; i < diff.size(); i++) {
    res[i] = res[i - 1] + diff[i];
}

res = [0] * len(diff)
# construct the result array based on the difference array
res[0] = diff[0]
for i in range(1, len(diff)):
    res[i] = res[i - 1] + diff[i]

res := make([]int, len(diff))
// construct the result array based on the difference array
res[0] = diff[0]
for i := 1; i < len(diff); i++ {
    res[i] = res[i-1] + diff[i]
}

var res = new Array(diff.length);
// construct the result array based on the difference array
res[0] = diff[0];
for (var i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

By constructing a difference array diff in this way, you can quickly perform range increment and decrement operations. If you want to add 3 to all elements in the range nums[i..j], you only need to execute diff[i] += 3 and then diff[j+1] -= 3:

The principle is straightforward. Recall the process of deriving the nums array from the diff array. The operation diff[i] += 3 means adding 3 to all elements from nums[i..]. Then diff[j+1] -= 3 means subtracting 3 from all elements in nums[j+1..]. Combined, this effectively adds 3 to all elements in nums[i..j].

By spending O(1) time to modify the diff array, you effectively modify the entire range in nums. Multiple modifications to diff can be applied, and by backtracking through the diff array, you can obtain the modified results of nums.

Now, let's abstract the difference array into a class, which includes an increment method and a result method:

// Difference Array Utility Class
class Difference {
    // difference array
    private int[] diff;
    
    // input an initial array, range operations will be performed on this array
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // construct the difference array based on the initial array
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // increment the closed interval [i, j] by val (can be negative)
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    // return the result array
    public int[] result() {
        int[] res = new int[diff.length];
        // construct the result array based on the difference array
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

// Difference Array Tool Class
class Difference {
    // difference array
    private:
        vector<int> diff;
    
    // input an initial array, range operations will be performed on this array
    public:
        Difference(vector<int>& nums) {
            diff = vector<int>(nums.size());
            // construct the difference array based on the initial array
            diff[0] = nums[0];
            for (int i = 1; i < nums.size(); i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        // add val (can be negative) to the closed interval [i, j]
        void increment(int i, int j, int val) {
            diff[i] += val;
            if (j + 1 < diff.size()) {
                diff[j + 1] -= val;
            }
        }

        // return the result array
        vector<int> result() {
            vector<int> res(diff.size());
            // construct the result array based on the difference array
            res[0] = diff[0];
            for (int i = 1; i < diff.size(); i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
};

# Difference Array Tool Class
class Difference:
    # difference array
    def __init__(self, nums: List[int]):
        assert len(nums) > 0
        self.diff = [0] * len(nums)
        # construct the difference array based on the initial array
        self.diff[0] = nums[0]
        for i in range(1, len(nums)):
            self.diff[i] = nums[i] - nums[i - 1]

    # increment the closed interval [i, j] by val (can be negative)
    def increment(self, i: int, j: int, val: int) -> None:
        self.diff[i] += val
        if j + 1 < len(self.diff):
            self.diff[j + 1] -= val

    # return the result array
    def result(self) -> List[int]:
        res = [0] * len(self.diff)
        # construct the result array based on the difference array
        res[0] = self.diff[0]
        for i in range(1, len(self.diff)):
            res[i] = res[i - 1] + self.diff[i]
        return res

// Difference array utility class
type Difference struct {
    // difference array
    diff []int
}

// Input an initial array, interval operations will be performed on this array
func NewDifference(nums []int) *Difference {
    diff := make([]int, len(nums))
    // construct the difference array based on the initial array
    diff[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        diff[i] = nums[i] - nums[i-1]
    }
    return &Difference{diff: diff}
}

// Add val (can be negative) to the closed interval [i, j]
func (d *Difference) Increment(i, j, val int) {
    d.diff[i] += val
    if j+1 < len(d.diff) {
        d.diff[j+1] -= val
    }
}

// Return the result array
func (d *Difference) Result() []int {
    res := make([]int, len(d.diff))
    // construct the result array based on the difference array
    res[0] = d.diff[0]
    for i := 1; i < len(d.diff); i++ {
        res[i] = res[i-1] + d.diff[i]
    }
    return res
}

class Difference {
    constructor(nums) {
        // difference array
        this.diff = new Array(nums.length);
        // construct the difference array based on the initial array
        this.diff[0] = nums[0];
        for (let i = 1; i < nums.length; i++) {
            this.diff[i] = nums[i] - nums[i - 1];
        }
    }

    // increase the closed interval [i, j] by val (can be negative)
    increment(i, j, val) {
        this.diff[i] += val;
        if (j + 1 < this.diff.length) {
            this.diff[j + 1] -= val;
        }
    }

    // return the result array
    result() {
        let res = new Array(this.diff.length);
        // construct the result array based on the difference array
        res[0] = this.diff[0];
        for (let i = 1; i < this.diff.length; i++) {
            res[i] = res[i - 1] + this.diff[i];
        }
        return res;
    }
}

Pay attention to the if statement in the increment method:

void increment(int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < diff.length) {
        diff[j + 1] -= val;
    }
}

void increment(int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < sizeof(diff)/sizeof(int)) {
        diff[j + 1] -= val;
    }
}

def increment(i: int, j: int, val: int) -> None:
    diff[i] += val
    
    if j + 1 < len(diff):
        diff[j + 1] -= val

func increment(i int, j int, val int) {
    diff[i] += val
    if j+1 < len(diff) {
        diff[j+1] -= val
    }
}

var increment = function(i, j, val) {
    diff[i] += val;
    if (j + 1 < diff.length) {
        diff[j + 1] -= val;
    }
};

When j+1 >= diff.length, it means that the entire array starting from nums[i] will be modified. Therefore, there is no need to subtract val from the diff array anymore.

Algorithm Practice

Firstly, LeetCode problem #370 "Range Addition" directly tests the difference array technique:

370. Range Addition | LeetCode |

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

Example 1:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4]

Constraints:

• 1 <= length <= 105
• 0 <= updates.length <= 104
• 0 <= startIdxi <= endIdxi < length
• -1000 <= inci <= 1000

We can solve this problem by reusing the Difference class we implemented earlier:

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        // initialize nums with all zeros
        int[] nums = new int[length];
        // construct the difference array solution
        Difference df = new Difference(nums);
        
        for (int[] update : updates) {
            int i = update[0];
            int j = update[1];
            int val = update[2];
            df.increment(i, j, val);
        }
        
        return df.result();
    }
}

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        // initialize nums with all zeros
        vector<int> nums(length, 0);
        // construct the difference decomposition
        Difference df(nums);
        
        for (auto& update : updates) {
            int i = update[0];
            int j = update[1];
            int val = update[2];
            df.increment(i, j, val);
        }
        
        return df.result();
    }
};

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        # initialize nums to all zeros
        nums = [0] * length
        # construct the difference solution
        df = Difference(nums)
        
        for update in updates:
            i = update[0]
            j = update[1]
            val = update[2]
            df.increment(i, j, val)
        
        return df.result()

func getModifiedArray(length int, updates [][]int) []int {
    // initialize nums with all zeros
    nums := make([]int, length)
    // construct the difference array solution
    df := NewDifference(nums)

    for _, update := range updates {
        i := update[0]
        j := update[1]
        val := update[2]
        df.Increment(i, j, val)
    }

    return df.Result()
}

var getModifiedArray = function(length, updates) {
  // initialize nums to all zeros
  let nums = new Array(length).fill(0)
  // construct the difference solution
  let df = new Difference(nums)
  
  for(let update of updates) {
    let i = update[0]
    let j = update[1]
    let val = update[2]
    df.increment(i, j, val)
  }
  
  return df.result()
}

Of course, real algorithm problems may require us to make associations and abstractions from the question, and it won't be so straightforward to see that the difference array technique is needed. Let's take a look at LeetCode problem #1109 "Corporate Flight Bookings":

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

The function signature is as follows:

int[] corpFlightBookings(int[][] bookings, int n)

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n)

def corpFlightBookings(bookings: List[List[int]], n: int) -> List[int]:

func corpFlightBookings(bookings [][]int, n int) []int

var corpFlightBookings = function(bookings, n) {};

This problem seems to be going around in circles, but it's actually a difference array problem. Let me translate it for you:

You are given an input array nums of length n, where all elements are 0. Additionally, you are given a bookings array containing several triplets (i, j, k). Each triplet means you need to add k to all elements in the closed interval [i-1, j-1] of the nums array. Your task is to return the final nums array.

Looking at it this way, isn't it a standard difference array problem? We can directly reuse the class we just wrote:

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        // initialize nums to all 0's
        int[] nums = new int[n];
        // construct the difference solution
        Difference df = new Difference(nums);

        for (int[] booking : bookings) {
            // note that converting to array index should minus one
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int val = booking[2];
            // increase the range nums[i..j] by val
            df.increment(i, j, val);
        }
        // return the final result array
        return df.result();
    }
}

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // nums initialized to all zeros
        vector<int> nums(n);
        // construct the difference solution
        Difference df(nums);

        for (auto& booking : bookings) {
            // note that converting to array index should subtract one
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int val = booking[2];
            // increment the range nums[i..j] by val
            df.increment(i, j, val);
        }
        // return the final result array
        return df.result();
    }
};

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        # initialize nums with all zeros
        nums = [0] * n
        # construct the difference solution
        df = Difference(nums)

        for booking in bookings:
            # note that converting to array index should minus one
            i = booking[0] - 1
            j = booking[1] - 1
            val = booking[2]
            # increase the interval nums[i..j] by val
            df.increment(i, j, val)
        # return the final result array
        return df.result()

func corpFlightBookings(bookings [][]int, n int) []int {
    // initialize nums to all 0
    nums := make([]int, n)
    // construct the difference solution
    df := NewDifference(nums)

    for _, booking := range bookings {
        // note that converting to array index should minus one
        i := booking[0] - 1
        j := booking[1] - 1
        val := booking[2]
        // increment the section nums[i..j] by val
        df.Increment(i, j, val)
    }
    // return the final result array
    return df.Result()
}

var corpFlightBookings = function(bookings, n) {
    // initialize nums to all zeros
    let nums = Array(n).fill(0);
    // construct the difference solution
    let df = new Difference(nums);
    
    bookings.forEach(booking => {
        // note that converting to array index should subtract one
        let i = booking[0] - 1;
        let j = booking[1] - 1;
        let val = booking[2];
        // increment the range nums[i..j] by val
        df.increment(i, j, val);
    })

    // return the final result array
    return df.result();
};

This problem is solved.

There is another similar problem, which is LeetCode problem #1094 "Car Pooling". Here's a brief description of the problem:

You are a bus driver, and your bus has a maximum capacity of capacity. The bus route includes several stops. You are given a list of passenger trips int[][] trips, where trips[i] = [num, start, end] indicates that num passengers will board at stop start and alight at stop end. Your task is to determine if you can transport all passengers in one trip without exceeding the maximum capacity capacity.

The function signature is as follows:

boolean carPooling(int[][] trips, int capacity);

bool carPooling(vector<vector<int>>& trips, int capacity);

def carPooling(trips: List[List[int]], capacity: int) -> bool:

func carPooling(trips [][]int, capacity int) bool {}

var carPooling = function(trips, capacity) {

};

For example, given the input:

trips = [[2,1,5],[3,3,7]], capacity = 4

This cannot be completed in one trip because trips[1] can only accommodate 2 passengers at most; otherwise, the vehicle will be overloaded.

You might already be thinking of the difference array technique: trips[i] represents a set of range operations, where passengers boarding and alighting are equivalent to range additions and subtractions in an array; as long as all elements in the resulting array are less than capacity, it means all passengers can be transported without overloading.

The question is, what should be the length of the difference array (the number of stations)? The problem does not directly provide this, but it gives the range of data values:

0 <= trips[i][1] < trips[i][2] <= 1000

Station numbers start from 0 and go up to 1000, meaning there can be a maximum of 1001 stations. Therefore, we can directly set the length of our difference array to 1001, so the indices can cover all station numbers:

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // there are at most 1001 stations
        int[] nums = new int[1001];

        // construct the difference array solution
        Difference df = new Difference(nums);

        for (int[] trip : trips) {
            // number of passengers
            int val = trip[0];

            // passengers get on at station trip[1]
            int i = trip[1];

            // passengers have got off at station trip[2],
            // that is, the interval for passengers on the bus is [trip[1], trip[2] - 1]
            int j = trip[2] - 1;

            // perform the interval operation
            df.increment(i, j, val);
        }

        int[] res = df.result();

        // the bus should never be overloaded throughout the journey
        for (int i = 0; i < res.length; i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // there are at most 1001 stations
        vector<int> nums(1001);
        
        // construct the difference solution
        Difference df(nums);
        
        for (vector<int> trip : trips) {
            // number of passengers
            int val = trip[0];
            
            // passengers get on at station trip[1]
            int i = trip[1];
            
            // passengers have got off at station trip[2],
            // i.e., the interval for passengers on board is [trip[1], trip[2] - 1]
            int j = trip[2] - 1;
            
            // perform interval operation
            df.increment(i, j, val);
        }
        
        vector<int> res = df.result();
        
        // the bus should never be overloaded throughout
        for (int i = 0; i < res.size(); i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def carPooling(self, trips, capacity):
        # There are at most 1001 stations
        nums = [0] * 1001

        # Construct the difference array method
        df = [0] * len(nums)

        for trip in trips:
            # Number of passengers
            val = trip[0]
            # Passengers board at station trip[1]
            i = trip[1]
            # Passengers get off at station trip[2],
            # meaning passengers are on the car from [trip[1], trip[2] - 1]
            j = trip[2] - 1
            # Perform interval operations
            df[i] += val
            if j + 1 < len(df):
                df[j + 1] -= val

        for i in range(1, len(df)):
            df[i] += df[i - 1]

        # The bus should never be overloaded
        for i in range(len(df)):
            if capacity < df[i]:
                return False

        return True

func carPooling(trips [][]int, capacity int) bool {
    // there are at most 1001 stations
    nums := make([]int, 1001)
    
    // construct the difference solution
    df := NewDifference(nums)

    for _, trip := range trips {
        // number of passengers
        val := trip[0]
        
        // passengers get on at station trip[1]
        i := trip[1]
        
        // passengers have got off at station trip[2],
        j := trip[2] - 1
        
        // that is, the interval for passengers on the bus is [trip[1], trip[2] - 1]
        
        // perform interval operation
        df.Increment(i, j, val)
    }

    res := df.Result()

    // the bus should never be overloaded from start to finish
    for i := 0; i < len(res); i++ {
        if capacity < res[i] {
            return false
        }
    }
    return true
}

var carPooling = function(trips, capacity) {
    // there are at most 1001 stations
    var nums = new Array(1001).fill(0);

    // construct the difference solution
    var df = new Difference(nums);
        
    for (var trip of trips) {
        // number of passengers
        var val = trip[0];

        // passengers get on at station trip[1]
        var i = trip[1];

        // passengers have got off at station trip[2],
        var j = trip[2] - 1;
        // i.e., the interval for passengers on board is [trip[1], trip[2] - 1]

        // perform interval operation
        df.increment(i, j, val);
    }
        
    var res = df.result();
        
    // the bus should never be overloaded from start to finish
    for (var i = 0; i < res.length; i++) {
        if (capacity < res[i]) {
            return false;
        }
    }
    return true;
};

With this, the problem is also solved.

Both difference arrays and prefix sum arrays are common and clever algorithmic techniques, each suitable for different scenarios. They are easy for those who understand them, but challenging for those who don't. So, have you learned how to use difference arrays?