Number of Islands
The key idea
Every time you find a new land cell that has not been visited, that is the start of a brand-new island. Flood-fill the whole island so its cells are never counted again, then keep scanning.
Problem
You are given an m x n 2-D grid grid of '1's (land) and '0's (water). Return the number of islands.
An island is a group of land cells connected 4-directionally (up, down, left, right). You may assume all four edges of the grid are surrounded by water.
Land cells that touch only diagonally are not connected and belong to different islands.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'
Examples
Input: grid = [["1","1","0"],["1","0","0"],["0","0","0"]]
Output: 1
Input: grid = [["1","1","0","0"],["0","0","0","1"],["0","0","0","0"],["1","0","0","0"]]
Output: 3
Complexity
Time: O(m*n) Space: O(m*n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM