Difference Array
Corporate Flight Bookings
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;
}
}