Max Area of Island

Problem Statement

In the given problem, you are equipped with an m x n binary matrix named grid. This matrix consists of cells encoded as either 0 or 1. The cells marked with 1 represent land and form parts of an island when they are connected directly in horizontal or vertical directions — termed 4-directionally connected. An island's area is defined by the count of contiguous 1s forming that island, representing the number of cells that make up the landmass. The challenge is to compute the maximum area of an island present in the matrix. If no land (i.e., 1s) is found in the grid, the answer should be 0. This task requires efficient matrix traversal and area calculation strategies to determine the largest island's size properly.

Examples

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.

Approach and Intuition

To tackle the problem of finding the maximum area of an island in a 2D grid, here’s a step-by-step breakdown of a possible approach based on the provided examples and constraints:

1. Initialize Maximum Area: Start with a variable to store the maximum area encountered, initially set to zero.

2. Iterate Over the Grid: Traverse each cell in the grid using nested loops (outer loop to iterate over rows and inner loop for columns).

3. Check for Land: When a cell with 1 (land) is found, initiate an area calculation using either Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the entire island connected 4-directionally to this cell. During this search:

   • Mark cells that have been visited to avoid counting them multiple times, typically done by setting them to 0 or using a separate visited matrix.
   • For each valid adjacent land cell (1), increment the area count and continue the search from that cell.

4. Update Maximum Area: After the area for an island starting from the current cell is fully calculated, compare it to the maximum area recorded so far. If larger, update the maximum area.

5. Repeat Until Grid is Fully Traversed: Continue the above steps for all cells in the grid. The complexity will remain manageable due to the constraints provided (m, n <= 50), ensuring that operations on the grid are bounded.

6. Return the Result: Once every cell has been checked, return the maximum area found.

The intuition behind using DFS or BFS is their efficiency in exploring nodes or cells that meet specific criteria (in this case, finding and traversing all directly connected 1s). They are suitable for this problem because they effectively manage the exploration of connected components in a grid structure. The bounded size of the grid (maximum of 2500 cells) makes this approach feasible within the constraints without optimizations like union-find, which could otherwise be overkill for this problem.

Solutions

class Solution {
    public int getMaxArea(int[][] matrix) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        int[] xOffset = new int[]{1, -1, 0, 0};
        int[] yOffset = new int[]{0, 0, 1, -1};

        int maxArea = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1 && !visited[i][j]) {
                    int area = 0;
                    Stack<int[]> stack = new Stack<>();
                    stack.push(new int[]{i, j});
                    visited[i][j] = true;
                    while (!stack.isEmpty()) {
                        int[] pos = stack.pop();
                        int row = pos[0], col = pos[1];
                        area++;
                        for (int k = 0; k < 4; k++) {
                            int newRow = row + xOffset[k];
                            int newCol = col + yOffset[k];
                            if (0 <= newRow && newRow < matrix.length &&
                                    0 <= newCol && newCol < matrix[0].length &&
                                    matrix[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                                stack.push(new int[]{newRow, newCol});
                                visited[newRow][newCol] = true;
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
}