658. Closed Islands
A surveyor works with a rectangular grid where 1 marks land and 0 marks water. An island is a maximal group of land cells that are connected through shared sides (up, down, left or right); diagonal contact does not join cells. An island is closed when none of its cells lies in the first row, the last row, the first column or the last column, which means water separates it from the outside of the map on every side.
Return the number of closed islands. Islands that reach the edge of the map are not counted, and a map without land has zero closed islands. The solution should take O(R * C) time, O(R * C) extra space and avoid recursion.
Example 1
- Input:
- grid = [[0,0,0,0,0],[0,1,1,0,0],[0,0,0,0,0],[0,0,0,1,1],[0,0,0,0,0]]
- Output:
- 1
- Explanation:
The pair of land cells in the upper left is ringed by water and closed; the cells on the right touch the edge, so the answer is 1.
Example 2
- Input:
- grid = [[1,1,1],[1,0,1],[1,1,1]]
- Output:
- 0
- Explanation:
The ring of land touches the edge of the map, so it is not closed. The answer is 0.
Example 3
- Input:
- grid = [[0,0,0,0,0,0],[0,1,0,0,1,0],[0,0,0,0,0,0],[0,0,1,1,0,0],[0,0,0,0,0,0]]
- Output:
- 3
- Explanation:
None of the three islands reaches the edge of the map, so all of them are closed and the answer is 3.
Constraints
1 ≤ R, C ≤ 400
grid[i][j] is 0 or 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(R * C)
- Space
- O(R * C)