Solution For Max Area Of Island

Max Area of Island is a problem on Leetcode that challenges you to find the size of the largest island in a given matrix.

Problem Statement

You are given a 2D grid of 0’s and 1’s, where each 1 represents an island, and 0 represents water. Your task is to find the size of the largest island. An island is considered to be a group of connected 1’s and is formed by horizontally or vertically adjacent cells.

Solution Approach

One of the most optimal approaches for solving this problem is Depth-First Search (DFS). The approach is as follows:

• Traverse the entire grid using two nested loops to find a cell containing 1;
• If a cell containing 1 is found, visit all the connected cells in the same island using DFS. The approach for DFS is recursive. For each cell containing 1, call DFS recursively for its adjacent cells until we find all the connected cells of the island, and mark all the visited cells to avoid visiting them again;
• During the DFS traversal, keep track of the size of the island that is being visited. Once all the cells of one island are visited, the size is compared with the maximum size found so far;
• Repeat the process for all cells and islands.

Code Implementation

Below is the Python code implementation for the Max Area of Island problem using DFS.

def dfs(grid, i, j):
“””
Helper function to explore the grid using DFS
“””
if not (0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 1):
return 0
grid[i][j] = 0
return (1 + dfs(grid, i-1, j) + dfs(grid, i+1, j) + dfs(grid, i, j-1) + dfs(grid, i, j+1))

def maxAreaOfIsland(grid):
“””
Function to calculate maximum area of island using DFS
“””
max_area = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
max_area = max(max_area, dfs(grid, i, j))
return max_area

Here, dfs() is the helper function used to explore the grid using DFS. It returns the size of the island being visited. In maxAreaOfIsland() function, we loop through the grid and traverse through an island if it is present. We keep comparing the maximum size of an island and return it as the maximum size of the island in the input matrix.

Time Complexity

The time complexity of the above solution is O(N*M), where N and M are the number of rows and columns in the input matrix. This is because we need to traverse all the cells of the matrix at least once.

Space Complexity

The space complexity of the above solution is also O(N*M). This is because we are marking visited cells (changing them to 0’s) and using the recursive call stack for DFS.

Step by Step Implementation For Max Area Of Island

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 1) {
                    max = Math.max(max, getArea(grid, i, j));
                }
            }
        }
        return max;
    }
    
    public int getArea(int[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        return 1 + getArea(grid, i + 1, j) + getArea(grid, i - 1, j) + getArea(grid, i, j + 1) + getArea(grid, i, j - 1);
    }
}

def maxAreaOfIsland(grid):
    max_area = 0

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                max_area = max(max_area, get_area(grid, i, j))

    return max_area


def get_area(grid, i, j):
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
        return 0

    grid[i][j] = 0
    return 1 + get_area(grid, i + 1, j) + get_area(grid, i - 1, j) + get_area(grid, i, j + 1) + get_area(grid, i, j - 1)

var maxAreaOfIsland = function(grid) {
    let max = 0;
    
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1) {
                max = Math.max(max, getArea(grid, i, j));
            }
        }
    }
    
    return max;
};

function getArea(grid, i, j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] === 0) {
        return 0;
    }
    
    grid[i][j] = 0;
    
    return 1 + getArea(grid, i + 1, j) + getArea(grid, i - 1, j) + getArea(grid, i, j + 1) + getArea(grid, i, j - 1);
}

The following is a C++ solution for the leetcode problem max-area-of-island:

int maxAreaOfIsland(vector>& grid) {
    int max_area = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
                int area = getArea(grid, i, j);
                max_area = max(max_area, area);
            }
        }
    }
    return max_area;
}

int getArea(vector>& grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) {
        return 0;
    }
    
    grid[i][j] = 0;
    int area = 1;
    area += getArea(grid, i + 1, j);
    area += getArea(grid, i - 1, j);
    area += getArea(grid, i, j + 1);
    area += getArea(grid, i, j - 1);
    return area;
}

public class Solution {
    public int MaxAreaOfIsland(int[,] grid) {
        int maxArea = 0;
        for(int i = 0; i < grid.GetLength(0); i++) {
            for(int j = 0; j < grid.GetLength(1); j++) {
                if(grid[i,j] == 1) {
                    maxArea = Math.Max(maxArea, GetArea(grid, i, j));
                }
            }
        }
        return maxArea;
    }
    
    public int GetArea(int[,] grid, int i, int j) {
        if(i < 0 || i >= grid.GetLength(0) || j < 0 || j >= grid.GetLength(1) || grid[i,j] == 0) {
            return 0;
        }
        grid[i,j] = 0;
        return 1 + GetArea(grid, i+1, j) + GetArea(grid, i-1, j) + GetArea(grid, i, j+1) + GetArea(grid, i, j-1);
    }
}