Difference Array

Corporate Flight Bookings

Corporate Flight Bookings - LeetCode

So the idea is that every booking will be update to a range, and for range update, we have a special data structure Difference Array which could handle it in O(1) time.

In a nutshell, a difference array is an seperated array that stores the difference of adjacent elements of the original array. Think of it as the reverse of prefix sum array.

// original array            1 , 5, 7, 7, 9, 3
// difference array          1 , 4, 2, 0, 2, -6

Notice that diff[0] is always equal to orig[0].

So how to update to a range of items, e.g. you want to add x to every element in range [start, end], just do this:

diff[start-1] += x;
diff[end ] -= x;

In the end, just scan from the begining to the end of the diff array, and you’ll get the final vlaue of each element:

result[i] = result[i - 1] + diff[i]

Let’s apply the Difference Array to this specific problem:

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        for (int[] b : bookings) {
            res[b[0] - 1] += b[2];
            if (b[1] < n) res[b[1]] -= b[2];
        }
        for (int i = 1; i < n; ++i)
            res[i] += res[i - 1];
        return res;
    }
}