Mastering LeetCode: Counting the Number of Islands in a 2D Binary Grid
A Comprehensive Guide to Solving the Island Counting Problem Using Depth-First Search (DFS)
Introduction
Counting the number of islands in a 2D binary grid is a classic problem that appears frequently in coding interviews (LeetCode 200. Number of Islands). This problem challenges you to identify and count distinct islands in a grid where '1' represents land and '0' represents water. Solving this problem not only helps you practice depth-first search (DFS) algorithms but also enhances your problem-solving skills for tackling similar graph traversal problems.
In this article, we will delve into the problem statement, explore the DFS approach to solve it, and provide a step-by-step guide with a complete Python implementation.
Problem Statement
Here is the exact problem description from LeetCode:
Given an
m x n2D binary gridgridwhich 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: 1Example 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
Solution Overview
To solve this problem, we will use the Depth-First Search (DFS) algorithm. DFS is a graph traversal technique that explores as far as possible along each branch before backtracking.
By using DFS, we can explore and mark all connected land cells starting from any unvisited land cell, effectively identifying and counting distinct islands.
Step-by-Step Solution
Initial Setup
First, we initialize necessary variables:
rowsandcolsto store the dimensions of the grid.A set
visitedto keep track of visited cells to avoid redundant work.
Depth-First Search (DFS) Function
The DFS function will:
Take the current cell coordinates (
r,c) as parameters.Check boundary conditions and whether the cell is water or already visited.
Mark the cell as visited.
Recursively explore all four possible directions (up, down, left, right) to visit all connected land cells.
Main Loop to Count Islands
We iterate through each cell in the grid. For each unvisited land cell, we initiate a DFS to explore the entire island and increment our island count.
Complete Code Implementation
Here is the complete Python code with detailed comments for clarity:
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
def dfs(r: int, c: int):
# Boundary check and check if the cell is water or already visited
if (r < 0 or c < 0 or
r >= rows or c >= cols or
grid[r][c] == '0' or
(r, c) in visited):
return
# Mark the cell as visited
visited.add((r, c))
# Explore all four possible directions (up, down, left, right)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dr, dc in directions:
dfs(r + dr, c + dc)
islands = 0
# Iterate through each cell in the grid
for r in range(rows):
for c in range(cols):
# If the cell is land and not yet visited, it's a new island
if grid[r][c] == '1' and (r, c) not in visited:
islands += 1
# Perform DFS to mark all cells in this island as visited
dfs(r, c)
return islands
# Example usage
solution = Solution()
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
print(solution.numIslands(grid)) # Output: 3
Optimizations and Improvements
While the DFS approach is straightforward and effective, there are potential optimizations for large grids:
Iterative DFS: Using an explicit stack instead of recursion to avoid potential stack overflow in deep recursion.
Breadth-First Search (BFS): An alternative approach that uses a queue to explore the grid level by level.
Union-Find: A more advanced technique that uses a disjoint set data structure to group and count connected components efficiently.
Conclusion
In this article, we explored how to solve the Leetcode problem of counting the number of islands in a 2D binary grid using the Depth-First Search (DFS) algorithm. By breaking down the problem and providing a detailed step-by-step solution, we demonstrated how DFS can effectively traverse and mark connected components in a grid.
Mastering such problems is crucial for coding interviews, and practicing similar challenges will enhance your problem-solving skills and algorithmic thinking.
Happy coding!