Show problems as
Classic problem #1109MediumArrayPrefix Sum

Corporate Flight Bookings

Real-world version: Ink Drops on the Tile Strip
Tracked in this browser only
Read Corporate Flight Bookings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A press decorates a strip of n tiles laid out in a line and numbered 1 through n.

The head makes one pass for each entry of passes. The entry passes[i] = [first, last, drops] means that pass left drops drops of ink on tile first, on tile last, and on every tile lying between the two. A tile visited by several passes keeps the ink from all of them.

Return an array total of length n, where total[j] is the number of drops sitting on tile j + 1 once every pass has run.

Examples

Example 1

Input
passes = [[1, 3, 20], [2, 5, 7], [4, 5, 30]], n = 5
Output
[20, 27, 27, 37, 37]

Tile 1 is reached by the first pass alone, so it holds 20 drops. Tile 2 is reached by the first two passes, giving 27. Tile 4 is reached by the second and third passes, giving 37.

Example 2

Input
passes = [[2, 6, 4], [6, 6, 11], [1, 6, 1]], n = 6
Output
[1, 5, 5, 5, 5, 16]

The second pass covers tile 6 only. Tile 6 is the last tile of all three passes, so it collects 4 + 11 + 1 drops, while tile 1 is covered by the third pass alone.

Example 3

Input
passes = [[1, 2, 6], [5, 6, 6]], n = 6
Output
[6, 6, 0, 0, 6, 6]

No pass reaches tile 3 or tile 4, so those tiles stay bare, and the four tiles that are covered each get 6 drops.

Constraints

  • 1 <= n <= 2 * 10^4
  • 1 <= passes.length <= 2 * 10^4
  • passes[i].length == 3
  • 1 <= first <= last <= n
  • 1 <= drops <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def ink_per_tile(passes: list[list[int]], n: int) -> list[int]:
Java
public int[] inkPerTile(int[][] passes, int n)

More on the same topics