{x}
blog image

Max Area of Island

You are given an m x n binary matrix grid. 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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

 

Example 1:

Input: grid = [[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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

Problem: Max Area of Island

This problem asks to find the maximum area of an island in a given binary matrix. An island is a group of connected '1's (representing land) horizontally or vertically.

Approach

The most efficient approach to solve this problem is using Depth-First Search (DFS). We iterate through the grid. When we encounter a '1', it signifies the start of an island. We then perform a DFS to explore the entire connected island, counting the number of '1's. After exploring the entire island, we mark all visited cells as '0' to prevent revisiting them. We keep track of the maximum area encountered so far.

Detailed Explanation with Code

The code implements the DFS approach. The dfs function recursively explores the island starting from a given cell. It marks the current cell as visited ('0') and recursively calls itself for its adjacent cells (up, down, left, right). The base cases are when we encounter a '0' (water) or go out of bounds. The maxAreaOfIsland function iterates through the grid and calls dfs whenever it encounters a '1'.

Time Complexity: O(M*N), where 'M' and 'N' are the dimensions of the grid. Each cell is visited at most once.

Space Complexity: O(M*N) in the worst case, due to the recursive call stack of DFS. In the best case, the space complexity is O(1), when there are no islands or only very small islands.

Python3 Code

from itertools import pairwise
 
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
                return 0
            ans = 1
            grid[i][j] = 0 # Mark as visited
            ans += dfs(i + 1, j)
            ans += dfs(i - 1, j)
            ans += dfs(i, j + 1)
            ans += dfs(i, j - 1)
            return ans
 
        m, n = len(grid), len(grid[0])
        max_area = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j))
        return max_area

Java Code

class Solution {
    private int m;
    private int n;
    private int[][] grid;
 
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = Math.max(ans, dfs(i, j));
            }
        }
        return ans;
    }
 
    private int dfs(int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0; //Mark as visited
        return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1);
    }
}

C++ Code

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int max_area = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    max_area = max(max_area, dfs(grid, i, j));
                }
            }
        }
        return max_area;
    }
 
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0; //Mark as visited
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }
};

The other languages (Go, TypeScript, Rust) follow a similar structure, adapting the syntax to their respective languages. The core algorithm remains the same DFS approach.