How Far the Water Spreads

Hard

You are given a height map, an m × n integer matrix heights, and an array of water levels levels of length k. For each level levels[i], water is poured into the top-left cell (0, 0) and spreads: a cell gets flooded when its height is strictly below the level and it can be reached from (0, 0) by stepping between edge-adjacent cells, every one of which is also strictly below the level. If cell (0, 0) itself is not below the level, nothing floods. Return an array answer of length k where answer[i] is the number of flooded cells for level levels[i]. Each level is handled independently of the others.

Example 1

heights=[[2, 4], [3, 1]], levels=[3, 5, 1] → [1, 4, 0]

At level 3 only the starting cell (height 2) floods: both neighbours, 4 and 3, are not below the level. At level 5 the whole field floods, 4 cells. At level 1 even the starting cell sits above the water, so the answer is 0.

Example 2

heights=[[1, 9, 1], [1, 9, 1], [1, 1, 1]], levels=[2, 10] → [7, 9]

At level 2 the water flows around the wall of nines along the bottom row and fills all seven cells of height 1, the right column included. At level 10 all 9 cells flood.

Constraints

m = heights.length, n = heights[i].length
2 ≤ m, n ≤ 1000
4 ≤ m · n ≤ 10⁵
k = levels.length
1 ≤ k ≤ 10⁴
1 ≤ heights[i][j], levels[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Union Find Array Two Pointers Matrix Sorting Heap (Priority Queue)