Leetcode 1109. Corporate Flight Bookings

Problem statement

https://leetcode.com/problems/corporate-flight-bookings/

Solution

Let us keep differences of array, we can update them in O(1) and evaluate cumulative sum in the end.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def corpFlightBookings(self, B, n):
        diff = [0]*(n + 1)
        for x, y, s in B:
            diff[x-1] += s
            diff[y] -= s
        return list(accumulate(diff))[:-1]