200. Number of Islands
https://leetcode.com/problems/number-of-islands/
Medium
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Problem
Given a 2D array where 1 represents land and 0 represents water, islands are surrounded by water and formed by connecting adjacent land cells horizontally or vertically. How many islands are in this 2D array?
Approach
We visit all land and water cells. When we encounter land, we flood-fill all its neighbors to water so we won’t double-count islands on subsequent visits.
- Write a nested loop to visit all elements.
- Declare an ans variable to hold the result.
- When encountering a ‘1’, increment ans by 1.
- Update all connected ‘1’s to ‘0’ — treat them as water on future visits.
- Return ans.
Source Code
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
m := len(grid)
n := len(grid[0])
ans := 0
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if grid[x][y] == '1' {
ans += 1
dfs(grid, x, y, m, n)
}
}
}
return ans
}
func dfs(grid [][]byte, x, y, m, n int) {
if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == '0' {
return
}
grid[x][y] = '0'
dfs(grid, x + 1, y, m, n)
dfs(grid, x - 1, y, m, n)
dfs(grid, x, y + 1, m, n)
dfs(grid, x, y - 1, m, n)
}
Closing
Do you have a better or simpler solution?
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
