Intermediate Level
Implement the numberOfIslandsMatrix method that counts islands in a binary matrix.
The input contains a 2D grid with rows rows and cols columns.
Each cell contains either 1 for land or 0 for water. Your task is to count how many islands are present in the grid.
An island is formed by connected land cells. Cells are connected only horizontally or vertically, not diagonally.
Example 1
Input
grid (int[][]) =
[[1,1,0],[0,1,0],[1,0,1]]rows (int) =
3cols (int) =
3Returns (int)
3Example 2
Input
grid (int[][]) =
[[1,1],[1,1]]rows (int) =
2cols (int) =
2Returns (int)
1Example 3
Input
grid (int[][]) =
[[1,0],[0,1]]rows (int) =
2cols (int) =
2Returns (int)
2Scan the grid cell by cell.
When you find a land cell that has not been visited, it means a new island has started. Increase the island count, then use DFS or BFS to visit all land cells connected to that island.
After all connected land cells are marked as visited, continue scanning for the next unvisited land cell.
Pseudocode:
function numberOfIslandsMatrix(grid, rows, cols):
visited = rows by cols matrix filled with false
islands = 0
for row from 0 to rows - 1:
for col from 0 to cols - 1:
if grid[row][col] == 1 AND visited[row][col] == false:
islands++
dfs(row, col)
return islands
function dfs(row, col):
if row or col is outside grid:
return
if grid[row][col] == 0 OR visited[row][col] == true:
return
visited[row][col] = true
dfs(row - 1, col)
dfs(row + 1, col)
dfs(row, col - 1)
dfs(row, col + 1)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run