Enclosed Lagoons
MediumGraphs
Problem
On a satellite map grid, 1 is land and 0 is water. A body of water is a group of water cells connected horizontally or vertically.
A body of water is a lagoon when none of its cells lies on the edge of the map, so it is completely enclosed by land. Return the number of lagoons.
Example 1
- Input:
- grid = [[1,1,1,1,1],[1,0,0,1,1],[1,1,1,1,0],[1,0,1,0,1],[1,1,1,1,1]]
- Output:
- 3
The lagoons are {(1,1),(1,2)}, {(3,1)} and {(3,3)}. The water at (2,4) is on the edge, so it is open sea.
Example 2
- Input:
- grid = [[0,0],[0,0]]
- Output:
- 0
Constraints
- 1 ≤ rows, cols ≤ 200
- grid[r][c] is 0 or 1
Hint
Show the first hint
This is island counting on the water cells, with a filter.
Walkthrough
How to approach it
01Clarify before coding
- Is connectivity 4-directional? Yes.
- Does diagonal contact with the edge matter? No, only a water cell that is itself on the edge.
- May I modify the grid? Yes; otherwise copy it first.
02Brute force
For each water component, traverse it and record whether any cell is on the edge; count those that never touch it.
Cost: Already O(r · c) if done carefully; the trap is an early return when the edge is found, which leaves part of the component unvisited and later counted again.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.