Difference Array Technique

labuladongOriginalAbout 5971 words

This article will resolve

LeetCode	Difficulty
1094. Car Pooling	🟠
1109. Corporate Flight Bookings	🟠
370. Range Addition🔒	🟠

Prerequisites

Before reading this article, you should first study:

The Prefix Sum Technique is mainly used when the original array will not be modified, but there are frequent queries for the cumulative sum of a certain interval. The core code is as follows:

java 🟢

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];
    }
}

cpp 🤖

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];
    }
};

python 🤖

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]

go 🤖

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]
}

javascript 🤖

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 traversing the entire interval.

This article discusses an algorithmic technique very similar to the prefix sum concept called the "difference array." The primary application of the difference array is when there is a need to frequently increase or decrease elements of a certain interval in the original array.

For example, if you are given an input array nums, and then asked to add 1 to the entire interval nums[2..6], subtract 3 from nums[3..9], add 2 to nums[0..4], and so on...

After a series of operations, you're asked what the final values of the nums array are.

The conventional approach is straightforward: if you're asked to add val to the interval nums[i..j], you could use a for-loop to add val to each element in that range. However, this approach has a time complexity of $O(N)$ . Given the frequent modifications to nums in this scenario, this method would be inefficient.

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

java 🟢

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];
}

cpp 🤖

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];
}

python 🤖

# 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]

go 🤖

// 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]
}

javascript 🤖

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:

java 🟢

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];
}

cpp 🤖

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];
}

python 🤖

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]

go 🤖

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]
}

javascript 🤖

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:

java 🟢

// 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;
    }
}

cpp 🤖

// 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;
        }
};

python 🤖

# 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

go 🤖

// 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
}

javascript 🤖

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:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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

When j+1 >= diff.length, it indicates that modifications are applied to nums[i] and beyond, thus there's no need to subtract val from the diff array anymore.

Algorithm Practice

LeetCode Problem 370 "Range Addition" directly tests the differential array technique. It provides an input nums array of length n, with all initial elements set to 0, and asks you to perform increment and decrement operations on interval elements, finally returning the resulting nums array.

You can simply copy our implemented Difference class to solve it:

java 🟢

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        // nums initialized to all 0s
        int[] nums = new int[length];
        // construct difference method
        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 Difference {
        // difference array
        private int[] diff;

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

        // increment 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;
            }
        }

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

}

cpp 🤖

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

    class Difference {
        // difference array
        vector<int> diff;

    public:
        Difference(const vector<int>& nums) {
            assert(!nums.empty());
            diff.resize(nums.size());
            // construct difference array
            diff[0] = nums[0];
            for (size_t i = 1; i < nums.size(); ++i) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

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

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

python 🤖

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

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

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

        def result(self) -> List[int]:
            res = [0] * len(self.diff)
            # construct result array based on 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

go 🤖

func getModifiedArray(length int, updates [][]int) []int {
    // nums initialized to all 0s
    nums := make([]int, length)
    // construct difference method
    df := NewDifference(nums)
    for _, update := range updates {
        i, j, val := update[0], update[1], update[2]
        df.Increment(i, j, val)
    }
    return df.Result()
}

// Difference defines a difference array
// difference array
type Difference struct {
    diff []int
}

// NewDifference creates a Difference instance
func NewDifference(nums []int) *Difference {
    assert(len(nums) > 0)
    diff := make([]int, len(nums))
    // construct difference array
    diff[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        diff[i] = nums[i] - nums[i-1]
    }
    return &Difference{diff: diff}
}

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

// Result constructs the result array based on the difference array
func (d *Difference) Result() []int {
    res := make([]int, len(d.diff))
    // construct result array based on 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
}

// assert is a utility function to ensure a condition is met
func assert(condition bool) {
    if !condition {
        panic("condition failed")
    }
}

javascript 🤖

var getModifiedArray = function(length, updates) {
    // nums initialized to all 0s
    let nums = new Array(length).fill(0);
    // construct difference method
    let df = new Difference(nums);

    // Correctly using the prototype methods of Difference
    for (let update of updates) {
        df.increment(update[0], update[1], update[2]);
    }
    return df.result();
};

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

// Define increment method for Difference
Difference.prototype.increment = function(i, j, val) {
    // increment closed interval [i, j] by val (can be negative)
    this.diff[i] += val;
    if (j + 1 < this.diff.length) {
        this.diff[j + 1] -= val;
    }
};

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

Of course, real algorithm problems may require us to abstract and associate with the problem rather than directly revealing the use of differential array techniques. Here is LeetCode Problem 1109 "Corporate Flight Bookings":

1109. Corporate Flight Bookings | LeetCode | 🟠

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [first_i, last_i, seats_i] represents a booking for flights first_i through last_i (inclusive) with seats_i seats reserved for each flight in the range.

Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i.

Example 1:

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]

Example 2:

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]

Constraints:

1 <= n <= 2 * 10⁴
1 <= bookings.length <= 2 * 10⁴
bookings[i].length == 3
1 <= first_i <= last_i <= n
1 <= seats_i <= 10⁴

The function signature is as follows:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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

This problem seems to be twisting around, but it is essentially about the difference array. 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 that 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.

Note

Since the problem specifies that n starts counting from 1, while array indices start from 0, for the input triplet (i, j, k), the corresponding array interval should be [i-1, j-1].

Upon closer inspection, isn't this a standard difference array problem? We can directly reuse the class we wrote earlier:

java 🟢

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

        for (int[] booking : bookings) {
            // note that converting to array index needs to 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 Difference {
        // difference array
        private int[] diff;

        public Difference(int[] nums) {
            assert nums.length > 0;
            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];
            }
        }

        // 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;
            }
        }

        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;
        }
    }

}

cpp 🤖

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // initialize nums as all 0
        vector<int> nums(n, 0);
        // construct the difference array
        Difference df(nums);

        for (const auto& booking : bookings) {
            // note that converting to array index needs to 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();
    }

private:
    class Difference {
        // difference array
        vector<int> diff;

    public:
        Difference(const vector<int>& nums) {
            assert(!nums.empty());
            diff.resize(nums.size());
            // construct the difference array
            diff[0] = nums[0];
            for (size_t i = 1; i < nums.size(); ++i) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

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

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

python 🤖

class Solution:
    def corpFlightBookings(self, bookings, n):
        # initialize nums as all 0
        nums = [0] * n
        # construct the difference array
        df = self.Difference(nums)

        for booking in bookings:
            # note that converting to array index needs to subtract one
            i = booking[0] - 1
            j = booking[1] - 1
            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 Difference:
        # difference array
        def __init__(self, nums):
            assert len(nums) > 0
            self.diff = [0] * len(nums)
            # construct the difference 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, j, val):
            self.diff[i] += val
            if j + 1 < len(self.diff):
                self.diff[j + 1] -= val

        def result(self):
            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

go 🤖

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

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

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

func NewDifference(nums []int) *Difference {
    if len(nums) == 0 {
        panic("nums length must be greater than 0")
    }
    diff := make([]int, len(nums))
    // construct the difference array
    diff[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        diff[i] = nums[i] - nums[i-1]
    }
    return &Difference{diff}
}

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

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
}

javascript 🤖

var corpFlightBookings = function(bookings, n) {
    // initialize nums as all 0
    let nums = new Array(n).fill(0);
    // construct the difference array
    let df = new Difference(nums);

    for (let booking of bookings) {
        // note that converting to array index needs to 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();
};

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

    // increment 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;
        }
    }

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

This problem is solved.

There is another similar problem, LeetCode problem 1094 "Car Pooling":

1094. Car Pooling | LeetCode | 🟠

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengers_i, from_i, to_i] indicates that the i^th trip has numPassengers_i passengers and the locations to pick them up and drop them off are from_i and to_i respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Example 1:

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

Example 2:

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

Constraints:

1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengers_i <= 100
0 <= from_i < to_i <= 1000
1 <= capacity <= 10⁵

The function signature is as follows:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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:

java 🟢

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // at most there are 1000 stops
        int[] nums = new int[1001];
        // construct the difference array method
        Difference df = new Difference(nums);

        for (int[] trip : trips) {
            // number of passengers
            int val = trip[0];
            // passengers get on at stop trip[1]
            int i = trip[1];
            // passengers get off at stop trip[2],
            // meaning the interval passengers are on the car is [trip[1], trip[2] - 1]
            int j = trip[2] - 1;
            // perform interval operation
            df.increment(i, j, val);
        }

        int[] res = df.result();

        // the car should never exceed its capacity
        for (int i = 0; i < res.length; i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }

    // difference array utility class
    class Difference {
        // difference array
        private int[] diff;

        // input an initial array, interval 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;
        }
    }

}

cpp 🤖

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // at most there are 1000 stops
        vector<int> nums(1001, 0);
        // construct the difference array method
        Difference df(nums);

        for (const auto& trip : trips) {
            // number of passengers
            int val = trip[0];
            // passengers get on at stop trip[1]
            int i = trip[1];
            // passengers get off at stop trip[2],
            // meaning the interval passengers are on the car 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 car should never exceed its capacity
        for (int i = 0; i < res.size(); i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }

    // difference array utility class
    class Difference {
    private:
        // difference array
        vector<int> diff;

    public:
        // input an initial array, interval operations will be performed on this array
        Difference(vector<int>& nums) {
            assert(!nums.empty());
            diff.resize(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];
            }
        }

        // increment the closed interval [i, j] by val (can be negative)
        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;
        }
    };
};

python 🤖

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # at most there are 1000 stops
        nums = [0] * 1001
        # construct the difference array method
        df = self.Difference(nums)

        for trip in trips:
            # number of passengers
            val = trip[0]
            # passengers get on at stop trip[1]
            i = trip[1]
            # passengers get off at stop trip[2],
            # meaning the interval passengers are on the car is [trip[1], trip[2] - 1]
            j = trip[2] - 1
            # perform interval operation
            df.increment(i, j, val)

        res = df.result()

        # the car should never exceed its capacity
        for i in range(len(res)):
            if capacity < res[i]:
                return False
        return True

    # difference array utility class
    class Difference:
        # difference array
        def __init__(self, nums: List[int]):
            # input an initial array, interval operations will be performed on this array
            # construct the difference array based on the initial array
            self.diff = [nums[0]] + [nums[i] - nums[i - 1] for i in range(1, len(nums))]

        # 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 = [self.diff[0]]
            # construct the result array based on the difference array
            for i in range(1, len(self.diff)):
                res.append(res[i - 1] + self.diff[i])
            return res

go 🤖

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

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

    res := df.Result()

    // the car should never exceed its capacity
    for _, v := range res {
        if capacity < v {
            return false
        }
    }
    return true
}

// difference array utility class
type Difference struct {
}

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

// increment the closed interval [i, j] by val (can be negative)
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 {
    // construct the result array based on the difference array
    res := make([]int, len(d.diff))
    res[0] = d.diff[0]
    for i := 1; i < len(d.diff); i++ {
        res[i] = res[i-1] + d.diff[i]
    }
    return res
}

javascript 🤖

var carPooling = function(trips, capacity) {
    // at most there are 1000 stops
    const nums = new Array(1001).fill(0);
    // construct the difference array method
    const df = new Difference(nums);

    for (const trip of trips) {
        // number of passengers
        const val = trip[0];
        // passengers get on at stop trip[1]
        const i = trip[1];
        // passengers get off at stop trip[2],
        // meaning the interval passengers are on the car is [trip[1], trip[2] - 1]
        const j = trip[2] - 1;
        // perform interval operation
        df.increment(i, j, val);
    }

    const res = df.result();

    // the car should never exceed its capacity
    for (let i = 0; i < res.length; i++) {
        if (capacity < res[i]) {
            return false;
        }
    }
    return true;
};

// difference array utility class
class Difference {
    // input an initial array, interval operations will be performed on this array
    // construct the difference array based on the initial array
    constructor(nums) {
        // difference array
        this.diff = [...nums];
        this.diff[0] = nums[0];
        for (let i = 1; i < nums.length; i++) {
            this.diff[i] = nums[i] - nums[i - 1];
        }
    }

    // increment 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() {
        const 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;
    }
}

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?

Difference Array Technique

1094. 拼车 https://leetcode.cn/problems/car-pooling

1094. Car Pooling https://leetcode.com/problems/car-pooling

1109. 航班预订统计 https://leetcode.cn/problems/corporate-flight-bookings

1109. Corporate Flight Bookings https://leetcode.com/problems/corporate-flight-bookings

370. 区间加法 https://leetcode.cn/problems/range-addition

370. Range Addition https://leetcode.com/problems/range-addition

Algorithm Practice