Show problems as
Classic problem #2503HardArrayTwo PointersBreadth-First SearchUnion-FindSortingHeap (Priority Queue)Matrix

Maximum Number of Points From Grid Queries

Real-world version: Cells Cleared Under a Depth Budget
Tracked in this browser only
Read Maximum Number of Points From Grid Queries on LeetCode(opens in a new tab)

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

A survey grid records the silt depth of each cell, given as grid with m rows and n columns.

A dredger works one budget at a time. For a budget b it starts at the cell in row 0, column 0 and repeatedly moves to a cell sharing an edge with a cell it has already cleared. A cell may be cleared only when its recorded depth is strictly less than b, and that includes the starting cell: if the starting cell is not shallow enough, nothing is cleared at all. Each cell is counted once however often it is visited.

queries[i] holds the budget for the i-th run, and the runs are independent of each other. Return an array cleared where cleared[i] is how many cells the i-th run can clear.

Examples

Example 1

Input
grid = [[1, 2, 3], [2, 5, 7], [3, 5, 1]], queries = [5, 6, 2]
Output
[5, 8, 1]

Under a budget of 5 the dredger clears the cells recording 1, 2, 3, 2 and 3, which is five cells. Under a budget of 2 only the opening cell recording 1 is shallow enough, so one cell is cleared.

Example 2

Input
grid = [[5, 2], [1, 1]], queries = [3]
Output
[0]

The opening cell records a depth of 5, which is not below the budget of 3, so nothing at all is cleared.

Example 3

Input
grid = [[1, 2, 9], [9, 3, 9], [5, 4, 9]], queries = [6]
Output
[5]

The dredger clears 1, then 2 to its right, then 3 below that, then 4 below that, then 5 to the left of the 4, which is five cells.

Constraints

  • 2 <= grid.length <= 1000
  • 2 <= grid[0].length <= 1000
  • Every row of grid has the same length
  • 1 <= queries.length <= 10^4
  • 1 <= grid[i][j] <= 10^6
  • 1 <= queries[i] <= 10^6

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 cells_cleared(grid: list[list[int]], queries: list[int]) -> list[int]:
Java
public int[] cellsCleared(int[][] grid, int[] queries)

More on the same topics