Number of Islands

Explanation & Solution

Description

Given an m x n 2D binary 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 surrounded by water.

Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

Output: 1

Explanation: There is one island formed by all the connected '1's in the top-left region.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'

Approach

Graphs pattern

1. Initialize Variables

Get rows and cols from the grid dimensions
Set count = 0 to track the number of islands

2. Iterate Through Every Cell

Loop through each cell (r, c) in the grid
When we find a cell with value "1", we have discovered a new island
Increment count by 1

3. Flood Fill with DFS

From the discovered "1" cell, run a DFS to visit all connected land cells
At each visited cell, mark it as "0" (water) to prevent revisiting
Recursively explore all four directions: up, down, left, right

4. DFS Base Case

If the current position is out of bounds, return
If the current cell is "0" (water or already visited), return
Otherwise, mark the cell as visited and continue exploring neighbors

5. Return the Count

After scanning every cell in the grid, count holds the total number of islands
Each island was counted exactly once when its first "1" cell was found

Key Insight

The core idea is that each DFS call "sinks" an entire island by turning all its "1" cells into "0" cells, so we only count it once

Time

O(m * n)each cell is visited at most twice (once in the loop, once in DFS)

Space

O(m * n)in the worst case the recursion stack can be as deep as the number of cells

Visualization

Input:

DFS Traversal4×5 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

57 steps

Solution Code

Max Area of Island