Number of Islands
Problem Description
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
Output: 1
Example 2:
Input: grid
Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Solve it on LeetCode
Approaches
1. DFS Approach
Intuition:
The problem can be effectively solved by considering the grid as a graph. Here each '1' is a land and '0' is water. An island is simply a connected component of '1's, thus our goal is to count these connected components. Depth First Search (DFS) can be used to traverse each island starting from an unexplored piece of land ('1') and marking all the connected lands to avoid multiple counting.
Steps:
- Traverse each cell in the grid.
- When a '1' is found, initiate a DFS (or flood fill) from there, marking all connected '1's as visited by changing them to '0'.
- Each DFS initiation indicates a new island.
Code:
- Time Complexity: O(M * N) where M is the number of rows and N is the number of columns.
- Space Complexity: O(M * N) in worst case for the recursion stack.
2. BFS Approach
Intuition:
Similar to DFS, the Breadth First Search (BFS) approach is another way to traverse the islands. Instead of traversing deeply through each piece of land, BFS explores all the neighbors of a current land and queues them for further exploration.
Steps:
- Traverse the grid to identify an unvisited '1'.
- Use a queue to process all adjacent lands to explore the whole island.
- Mark all visited lands to ensure no double counting.
Code:
- Time Complexity: O(M * N) where M is the number of rows and N is the number of columns.
- Space Complexity: O(min(M, N)) for the BFS queue.
3. Union-Find Approach
Intuition:
This approach uses the Union-Find (Disjoint Set Union) data structure which is optimal when working with connected components problems. Each cell containing a '1' can be initially thought of as its own island, and then we connect lands that are adjacent, effectively reducing the island count when we union two lands.
Steps:
- Initialize each '1' as its own set.
- Union adjacent lands thereby reducing the total number of islands.
- The final number of unique parent sets represents the number of islands.
Code:
- Time Complexity: O(M * N * alpha(M * N)) where alpha is the Inverse Ackermann function, which is nearly constant for all practical purposes.
- Space Complexity: O(M * N) due to the parent and rank arrays.