Show problems as
Classic problem #598EasyArrayMath

Range Addition II

Real-world version: Trays Watered The Most Times
Tracked in this browser only
Read Range Addition II on LeetCode(opens in a new tab)

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

A greenhouse holds a rectangular block of seedling trays with rows rows and cols columns. Rows are numbered 1 to rows from the back wall forward, columns 1 to cols from the left wall rightward.

The irrigation arm runs a list of watering passes. Pass [a, b] sweeps the corner block anchored at row 1 and column 1: it waters every tray whose row number is at most a and whose column number is at most b, adding one to that tray's watering count. Every tray starts at a count of 0.

After all passes have run, return how many trays share the highest watering count in the greenhouse. If passes is empty, every tray is still tied on a count of 0.

Examples

Example 1

Input
rows = 4, cols = 5, passes = [[3, 2], [2, 4]]
Output
4

The first pass waters rows 1 to 3 and columns 1 to 2, the second waters rows 1 to 2 and columns 1 to 4. Trays (1,1), (1,2), (2,1) and (2,2) end on a count of 2 and no tray reaches 3, so four trays share the highest count.

Example 2

Input
rows = 6, cols = 7, passes = [[2, 7], [6, 3]]
Output
6

Trays in rows 1 to 2 and columns 1 to 3 are touched by both passes, giving them a count of 2, while every other watered tray sits at 1. That block holds six trays.

Example 3

Input
rows = 3, cols = 4, passes = []
Output
12

No pass runs, so all twelve trays still hold a count of 0 and every one of them ties for the highest count.

Constraints

  • 1 <= rows, cols <= 4 * 10^4
  • 0 <= passes.length <= 10^4
  • passes[i].length == 2
  • 1 <= passes[i][j] <= 4 * 10^4
  • Pass i is given as [a_i, b_i] with a_i at most rows and b_i at most cols.
  • Under these bounds the returned count is at most 1.6 * 10^9.

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 max_watered_trays(rows: int, cols: int, passes: list[list[int]]) -> int:
Java
public int maxWateredTrays(int rows, int cols, int[][] passes)

More on the same topics