Difference Array

Abhinay Gupta
1 min readMay 4, 2023

--

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

--

--

Abhinay Gupta

Exploring personal growth, tech, and culture through engaging storytelling | Inspiring and connecting with readers worldwide.