How hard is LeetCode 1109. Corporate Flight Bookings?

LeetCode 1109. Corporate Flight Bookings is rated Medium on LeetCode.

What is the time complexity of LeetCode 1109. Corporate Flight Bookings?

The Python solution on this page runs in O(n), where n is the number of flights.

What is the space complexity of LeetCode 1109. Corporate Flight Bookings?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1109. Corporate Flight Bookings cover?

LeetCode 1109. Corporate Flight Bookings is tagged Array and Prefix Sum on LeetCode.

Corporate Flight Bookings — LeetCode 1109 Python Solution

MediumArrayPrefix Sum

Problem: #1109
Pattern: Prefix Sum
Reading time: 2 min
Source: leetcode.com

The problem

There are n flights that are labeled from 1 to n. You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.

Example

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

Python solution

Python

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans = [0] * n
        for first, last, seats in bookings:
            ans[first - 1] += seats
            if last < n:
                ans[last] -= seats
        return list(accumulate(ans))

Complexity

Measure	Complexity
Time	O(n), where n is the number of flights
Space	O(1) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1109. Corporate Flight Bookings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1109. Corporate Flight Bookings?: LeetCode 1109. Corporate Flight Bookings is rated Medium on LeetCode.
What is the time complexity of LeetCode 1109. Corporate Flight Bookings?: The Python solution on this page runs in O(n), where n is the number of flights.
What is the space complexity of LeetCode 1109. Corporate Flight Bookings?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1109. Corporate Flight Bookings cover?: LeetCode 1109. Corporate Flight Bookings is tagged Array and Prefix Sum on LeetCode.