💡 Problem Formulation: Given a 2D grid where ‘1’s (land) and ‘0’s (water) are mixed together, we want to compute the largest area of connected land, which we term as an island. The land horizontally or vertically adjacent to each other is considered connected. For example, in a grid [
["11000"], ["11000"], ["00100"], ["00011"]], the largest island has an area of 4.
Method 1: Depth-First Search (DFS) through Recursion
The Depth-First Search algorithm explores as far as possible along each path before backtracking, which is perfect for finding connected land. In Python, we can implement this using a recursive function that marks visited cells to avoid infinite loops.
Here’s an example:
def maxAreaOfIsland(grid):
def dfs(i, j):
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
grid[i][j] = 0
return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
return 0
areas = [dfs(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j]]
return max(areas) if areas else 0
grid = [[1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]]
print(maxAreaOfIsland(grid))
Output:
4
This snippet defines a function maxAreaOfIsland() that applies a DFS approach via the nested dfs() function. It recursively explores adjacent land cells and marks them as visited by setting the cell value to 0. The areas list comprehension calculates the sizes of all islands, and the function returns the maximum.
Method 2: Iterative DFS using Stack
An iterative version of DFS can be engineered using a stack, which can help avoid potential recursion limit errors for very large grids. This method simulates the call stack mechanism of recursive DFS in a controlled manner.
Here’s an example:
def maxAreaOfIsland(grid):
def dfs(i, j):
stack = [(i, j)]
area = 0
while stack:
i, j = stack.pop()
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
grid[i][j] = 0 # Visit
area += 1
stack.extend([(i+1, j), (i-1, j), (i, j+1), (i, j-1)])
return area
return max([dfs(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j]], default=0)
grid = [[1,1,0,0,0], [1,1,0,0,0], [0,0,0,0,0], [0,0,0,1,1]]
print(maxAreaOfIsland(grid))
Output:
4
This code defines the maxAreaOfIsland() function which implements an iterative DFS by utilizing a stack. It explores each potential island’s area and tracks the visited cells by marking them with 0. The maximum area among all visits is determined and returned.
Method 3: Breadth-First Search (BFS)
Breadth-First Search explores the nearest nodes first and is typically implemented using a queue. This method works horizontally across the matrix before moving deeper, making it suitable for certain types of grid explorations.
Here’s an example:
from collections import deque
def maxAreaOfIsland(grid):
def bfs(i, j):
queue = deque([(i, j)])
area = 0
while queue:
i, j = queue.popleft()
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
grid[i][j] = 0 # Visit
area += 1
queue.extend([(i+1, j), (i-1, j), (i, j+1), (i, j-1)])
return area
return max([bfs(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j]], default=0)
grid = [[1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]]
print(maxAreaOfIsland(grid))
Output:
4
In this method, a Breadth-First Search is performed using a queue. The function bfs() is called for every potential starting point of an island, computing the area in a layer-by-layer manner and marking visited cells. The resulting areas are compared to find the largest island.
Method 4: Union-Find Algorithm
The Union-Find, or Disjoint Set algorithm, is an efficient method to determine connectivity in a graph, and thus, can be used to compute the largest island area by connecting adjacent land cells and tracking their collective area.
Here’s an example:
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0])
self.parent = {}
self.rank = {}
self.area = {}
for i in range(m):
for j in range(n):
if grid[i][j]:
id = i * n + j
self.parent[id] = id
self.rank[id] = 0
self.area[id] = 1
def find(self, id):
if self.parent[id] != id:
self.parent[id] = self.find(self.parent[id])
return self.parent[id]
def union(self, id1, id2):
parent1, parent2 = self.find(id1), self.find(id2)
if parent1 != parent2:
if self.rank[parent1] > self.rank[parent2]:
self.parent[parent2] = parent1
self.area[parent1] += self.area[parent2]
elif self.rank[parent1] < self.rank[parent2]:
self.parent[parent1] = parent2
self.area[parent2] += self.area[parent1]
else:
self.parent[parent2] = parent1
self.rank[parent1] += 1
self.area[parent1] += self.area[parent2]
def maxAreaOfIsland(grid):
if not grid or not grid[0]:
return 0
uf = UnionFind(grid)
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j]:
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]:
id1, id2 = i * n + j, ni * n + nj
uf.union(id1, id2)
return max(uf.area.values(), default=0)
grid = [[1,1,0,0,0], [1,1,0,0,0], [0,0,0,0,0], [0,0,0,1,1]]
print(maxAreaOfIsland(grid))
Output:
4
The Union-Find structure helps in grouping connected cells into discrete sets and tracking their sizes. The ID of each cell is its index in a flattened array representation of the grid. The union() operation merges sets, thereby increasing the count of the representative area upon each successful merging.
Bonus One-Liner Method 5: Using NumPy library
For those familiar with the NumPy library, it can be leveraged to perform fast, vectorized operations on the grid to find islands and their areas using image processing techniques.
Here’s an example:
import numpy as np
from scipy.ndimage import label
def maxAreaOfIsland(grid):
labeled_islands, num_islands = label(grid)
if num_islands == 0:
return 0
return max(np.sum(labeled_islands == i) for i in range(1, num_islands + 1))
grid = np.array([[1,1,0,0,0], [1,1,0,0,0], [0,0,0,0,0], [0,0,0,1,1]])
print(maxAreaOfIsland(grid))
Output:
4
This one-liner utilizes the label() function from the scipy.ndimage module to find connected regions (islands) and their labels, then computes the area of the largest island by summing the occurrences of each unique label.
Summary/Discussion
- Method 1: Depth-First Search (DFS) through Recursion. Strengths: intuitive implementation, recursive elegance. Weaknesses: susceptible to stack overflow on large inputs.
- Method 2: Iterative DFS using Stack. Strengths: efficient on larger grids, avoids recursion limits. Weaknesses: less elegant than recursive approach.
- Method 3: Breadth-First Search (BFS). Strengths: useful for shortest-path problems, performs well on denser islands. Weaknesses: might be slower for sparse grids.
- Method 4: Union-Find Algorithm. Strengths: very efficient for large number of queries, very fast on sparse grids. Weaknesses: complexity in understanding and setting up.
- Bonus Method 5: Using NumPy library. Strengths: very fast with vectorized operations, compact code. Weaknesses: requires additional libraries, might not be as intuitive.