Max area of the island: dfs and bfs approach

For the given island that’s represented in a matrix of 0's and 1's, we usually use a depth-first search or a breadth-first search algorithm to solve. Today, I’ll introduce how to solve and compare such a problem using both approaches.

Problem

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Try to solve it yourself: https://leetcode.com/problems/max-area-of-island/

DFS

While iterating the cell, we want to calculate the current island area that it could form. To do this, we can utilize the depth-first-search algorithm here. We’ll create a helper function, the input is the current position, the output is the area of adjacent islands. Here’s the process of executing:

• While iterating the grid, we pass the position of each cell to the helper function to get the island area;
• Inside the helper function, we need to consider several edge cases: 1) if the given position is out of range, we simple return 0; 2) if the given cell is water, we return 0 due to no island exist in the current cell
• To avoid circular search, we’ll use a set to record the visited islands

Code:

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        seen = set()
        def area(r, c):
            if not (0 <= r < len(grid) and 0 <= c < len(grid[0])
                    and (r, c) not in seen and grid[r][c]):
                return 0
            seen.add((r,c))
            return (1 + area(r+1, c) + area(r-1, c) +
                    area(r, c-1) + area(r, c+1))
        
        return max(area(r,c) for r in range(len(grid)) for c in range(len(grid[0])))

Analysis:

• Time Complexity: O(m*n), m is the number of rows and n is the number of the column in the given grid. There’re m*n cells in the given grid. Since we visited all cells, so the running time is O(m*n).
• Space complexity: O(m*n) , we introduce a set to record the visited cell. And memory is created during the recursion calls. The total space used is O(m*n) .

BFS

Unlike the dfs approach using a stack in recursion calls, the bfs approach usually utilizes a queue in the iteration. Here are the steps in bfs implementation:

• While iterating the grid, we check if the current cell is an island;
• If the cell is an island, we use a queue to record its adjacent island cells. If its adjacent cells are islands, we append the cell to the queue waiting for the next round’s checking.
• To avoid circular search, we’ll use a set to record the visited islands

Code:

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        seen = set()
        row_dir = [0,0,1,-1]
        col_dir = [1,-1,0,0]
        res = 0 
        
        for i in range(rows):
            for j in range(cols):
                if (i, j) not in seen and grid[i][j] == 1:
                    queue = [[i, j]]
                    area = 0
while queue:  
                        curr = queue.pop(0)
                        seen.add((curr[0], curr[1]))
                        area += 1
                        for k in range(4):
                            nr = curr[0] + row_dir[k]
                            nc = curr[1] + col_dir[k]
if nr >= 0 and nr < rows and nc >= 0 and nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
                                queue.append([nr, nc])
                                seen.add((nr, nc))
res = max(res, area)
        
        return res

Analysis:

• Time Complexity: O(m*n), m is the number of rows and n is the number of the column in the given grid. There’re m*n cells in the given grid. Since we visited all cells, so the running time is O(m*n).
• Space complexity: O(m*n) , we introduce a set to record the visited cell. And a queue is created in calculating the area. The total space used is O(m*n) .

Which solution do you prefer?

Reference

Max Area of Island - LeetCode