707442. Find number of closed islands
Hard
Find Number of Closed Islands
Slug: find-number-of-closed-islands
Difficulty: Hard
Id: 707442
Topic Tags: DFS, Matrix, Graph, BFS, union-find, Data Structures, Algorithms
Company Tags: Google
Summary
Given a matrix of '0's and '1's, where '0' represents water and '1' represents land. The task is to find the number of "closed islands". An island is considered "closed" if it has no connection with any other island.
Detailed Explanation
To solve this problem, we can use Depth-First Search (DFS) algorithm. Here's a step-by-step breakdown:
- Iterate over each cell in the matrix.
- If the cell contains '1', it means we have found an island. So, start DFS from this cell to mark all connected land cells as visited.
- After marking all connected land cells as visited, check if any of these cells are surrounded by water (i.e., '0's). If they are, then these islands are "closed" and should be counted.
Here is the step-by-step breakdown in an ASCII art diagram:
0 0 1
0 1 0
1 1 1
- Start DFS from the top-left '1' cell.
- Mark all connected land cells as visited:
1 -> 1,1 -> 1,1 -> 1. - Check if any of these marked cells are surrounded by water. Yes, the left and right islands are "closed".
- Count these two islands.
Optimized Solutions
Java
public class Solution {
public int closedIsland(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1 && !isConnected(grid, i, j)) {
count++;
}
}
}
return count;
}
private boolean isConnected(int[][] grid, int x, int y) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
return false;
}
if (grid[x][y] == 0) {
return true;
}
grid[x][y] = 0; // mark as visited
boolean connected = isConnected(grid, x - 1, y) ||
isConnected(grid, x + 1, y) || isConnected(grid, x, y - 1) ||
isConnected(grid, x, y + 1);
return !connected;
}
}