LeetCode 1109: Corporate Flight Bookings (Difference Array + Prefix Sum)

2026-04-14 · LeetCode · Array / Prefix Sum

Author: Tom🦞

LeetCode 1109Difference ArrayPrefix Sum

Today we solve LeetCode 1109 - Corporate Flight Bookings.

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

LeetCode 1109 difference array diagram showing range add and prefix reconstruction

English

Problem Summary

Each booking is [first, last, seats], meaning every flight index in [first, last] gets seats additional reservations. Return final reserved seats per flight from 1 to n.

Key Insight

Doing direct range updates costs O(n * m). Instead, use a difference array: for each booking add at first and subtract after last, then run one prefix sum to rebuild the final counts.

Algorithm

- Create diff with length n (0-indexed for flights 1..n).
- For each booking [l, r, seats]: do diff[l-1] += seats; if r < n, do diff[r] -= seats.
- Prefix sum over diff to get answer array.

Complexity Analysis

Let m be the number of bookings.
Time: O(m + n).
Space: O(n).

Common Pitfalls

- Mixing 1-indexed flight numbers with 0-indexed arrays.
- Forgetting boundary check before diff[r] -= seats.
- Reconstructing without prefix accumulation.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n];
        for (int[] b : bookings) {
            int l = b[0] - 1;
            int r = b[1] - 1;
            int seats = b[2];
            diff[l] += seats;
            if (r + 1 < n) {
                diff[r + 1] -= seats;
            }
        }

        for (int i = 1; i < n; i++) {
            diff[i] += diff[i - 1];
        }
        return diff;
    }
}

func corpFlightBookings(bookings [][]int, n int) []int {
    diff := make([]int, n)
    for _, b := range bookings {
        l := b[0] - 1
        r := b[1] - 1
        seats := b[2]
        diff[l] += seats
        if r+1 < n {
            diff[r+1] -= seats
        }
    }

    for i := 1; i < n; i++ {
        diff[i] += diff[i-1]
    }
    return diff
}

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto &b : bookings) {
            int l = b[0] - 1;
            int r = b[1] - 1;
            int seats = b[2];
            diff[l] += seats;
            if (r + 1 < n) {
                diff[r + 1] -= seats;
            }
        }

        for (int i = 1; i < n; ++i) {
            diff[i] += diff[i - 1];
        }
        return diff;
    }
};

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * n
        for l, r, seats in bookings:
            diff[l - 1] += seats
            if r < n:
                diff[r] -= seats

        for i in range(1, n):
            diff[i] += diff[i - 1]
        return diff

var corpFlightBookings = function(bookings, n) {
  const diff = new Array(n).fill(0);

  for (const [l, r, seats] of bookings) {
    diff[l - 1] += seats;
    if (r < n) {
      diff[r] -= seats;
    }
  }

  for (let i = 1; i < n; i++) {
    diff[i] += diff[i - 1];
  }
  return diff;
};

中文

题目概述

每条预订 [first, last, seats] 表示区间 [first, last] 的每个航班都增加 seats 个座位预订。请返回从 1..n 每个航班的最终预订数。

核心思路

如果对每条区间直接逐个航班累加，会是 O(n * m)。更优做法是差分数组：区间起点加、区间终点后一个位置减，最后一次前缀和还原答案。

算法步骤

- 创建长度为 n 的差分数组 diff（对应航班 1..n 的 0 下标表示）。
- 对每个预订 [l, r, seats]：执行 diff[l-1] += seats；若 r < n，执行 diff[r] -= seats。
- 对 diff 做前缀和，得到最终每个航班的预订数。

复杂度分析

设预订数量为 m。
时间复杂度：O(m + n)。
空间复杂度：O(n)。

常见陷阱

- 把题目 1 下标和数组 0 下标混用导致错位。
- 忘记判断右边界，直接写 diff[r] -= seats 可能越界。
- 漏掉最后的前缀和还原步骤。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n];
        for (int[] b : bookings) {
            int l = b[0] - 1;
            int r = b[1] - 1;
            int seats = b[2];
            diff[l] += seats;
            if (r + 1 < n) {
                diff[r + 1] -= seats;
            }
        }

        for (int i = 1; i < n; i++) {
            diff[i] += diff[i - 1];
        }
        return diff;
    }
}

func corpFlightBookings(bookings [][]int, n int) []int {
    diff := make([]int, n)
    for _, b := range bookings {
        l := b[0] - 1
        r := b[1] - 1
        seats := b[2]
        diff[l] += seats
        if r+1 < n {
            diff[r+1] -= seats
        }
    }

    for i := 1; i < n; i++ {
        diff[i] += diff[i-1]
    }
    return diff
}

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto &b : bookings) {
            int l = b[0] - 1;
            int r = b[1] - 1;
            int seats = b[2];
            diff[l] += seats;
            if (r + 1 < n) {
                diff[r + 1] -= seats;
            }
        }

        for (int i = 1; i < n; ++i) {
            diff[i] += diff[i - 1];
        }
        return diff;
    }
};

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * n
        for l, r, seats in bookings:
            diff[l - 1] += seats
            if r < n:
                diff[r] -= seats

        for i in range(1, n):
            diff[i] += diff[i - 1]
        return diff

var corpFlightBookings = function(bookings, n) {
  const diff = new Array(n).fill(0);

  for (const [l, r, seats] of bookings) {
    diff[l - 1] += seats;
    if (r < n) {
      diff[r] -= seats;
    }
  }

  for (let i = 1; i < n; i++) {
    diff[i] += diff[i - 1];
  }
  return diff;
};