Funcia
Lv.2bfsdfsgraphgrid

Rain Flowing to Both Seas

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A rectangular island is divided into H×WH \times W cells; heights[i][j] is the height of a cell. The top and left coasts touch the North-West Sea and the bottom and right coasts touch the South-East Sea.

Rain on a cell can flow to any horizontally or vertically adjacent cell whose height is less than or equal to the current one. A cell on the border flows into the sea on that side (e.g. the top row into the North-West Sea, the rightmost column into the South-East Sea).

Return the number of cells from which rain can reach both seas. Water may split and follow several paths.

Examples

heightsresult
[[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]7
[[3, 3, 3], [3, 1, 3], [3, 3, 3]]8
[[7]]1

Example 1 — The cells are (0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0).

Example 2 — The centre is a pit; the 8 border cells reach both seas along the flat coast.

Example 3 — A single cell touches every coast.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(heights: int[][]) → int

Constraints

  • 1≤H=1 \le H = heights.length ≤500\le 500
  • 1≤W=1 \le W = heights[i].length ≤500\le 500; all rows have the same length.
  • 0≤0 \le heights[i][j] ≤109\le 10^9

Expected complexity

Time
O(HW)
Space
O(HW)

Examples

heightsExpected
[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]7
[[3,3,3],[3,1,3],[3,3,3]]8
[[7]]1

Hint

Hint

Searching from every cell is O((HW)2)O((HW)^2). Search backwards instead: start a multi-source BFS from all top-row and left-column cells and step to a neighbour only if it is at least as high; the reached cells drain to the North-West Sea. Do the same from the bottom row and right column, and count cells marked by both searches. Use an explicit queue rather than recursion.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251108 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.