Problem Statement

• 695. Max Area of Island

Given an m x n binary matrix grid, find the maximum area of an island. An island is a group of 1's connected 4-directionally (horizontal or vertical). The area of an island is the count of 1 cells in that island. Return the maximum area among all islands, or 0 if no islands exist.

Key points:

• Islands are formed by connected 1s (land)
• Connection is only 4-directional (up, down, left, right)
• All edges are surrounded by water (0)
• Need to find the largest island by area (cell count)

Algorithm Walkthrough

This problem is solved using Depth-First Search (DFS) with the following approach:

Step 1: Iterate Through the Grid

• Traverse each cell in the grid
• When we encounter a 1, it's the start of a potential island

Step 2: DFS to Calculate Island Area

• From each 1 cell, perform DFS to explore all connected land cells
• Mark visited cells to avoid double counting (change 1 to 0)
• Count cells as we visit them to calculate the island's area

Step 3: Track Maximum Area

• Keep track of the maximum area found so far
• Update it whenever we find a larger island

DFS Process:

1. Base cases: Return 0 if out of bounds or current cell is 0
2. Mark as visited: Change current cell from 1 to 0
3. Explore neighbors: Recursively visit all 4 directions
4. Return area: Sum of current cell (1) + areas from all directions

Example Walkthrough:

For the grid with island of area 6:

[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]  <- This island has area 6
[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]  <- Connected to form area 6

When DFS hits the 1 at position (1,7), it explores all connected cells and counts 6 total cells.

Complexity Analysis

• Time Complexity: O(m × n)

  • We visit each cell at most once
  • Each cell is processed in constant time
  • DFS explores each land cell exactly once

• Space Complexity: O(m × n)

  • Worst case: entire grid is one island, DFS call stack depth = m × n
  • Average case: Much better when islands are smaller
  • No extra space needed besides recursion stack

Full Solution (Java)

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        // Iterate through each cell in the grid
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                // If we find land (1), calculate the area of this island
                if(grid[i][j] == 1) {
                    int currentArea = dfs(grid, i, j);
                    maxArea = Math.max(maxArea, currentArea);
                }
            }
        }

        return maxArea;
    }

    private int dfs(int[][] grid, int row, int col) {
        // Base cases: out of bounds or water/visited cell
        if(row < 0 || row >= grid.length || 
           col < 0 || col >= grid[0].length || 
           grid[row][col] == 0) {
            return 0;
        }

        // Mark current cell as visited by changing it to 0
        grid[row][col] = 0;

        // Explore all 4 directions and sum up the areas
        int area = 1; // Current cell counts as 1
        area += dfs(grid, row + 1, col); // Down
        area += dfs(grid, row - 1, col); // Up
        area += dfs(grid, row, col + 1); // Right
        area += dfs(grid, row, col - 1); // Left

        return area;
    }
}

Alternative: Using Visited Array (If Grid Modification Not Allowed)

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(grid[i][j] == 1 && !visited[i][j]) {
                    int currentArea = dfs(grid, visited, i, j);
                    maxArea = Math.max(maxArea, currentArea);
                }
            }
        }

        return maxArea;
    }

    private int dfs(int[][] grid, boolean[][] visited, int row, int col) {
        if(row < 0 || row >= grid.length || 
           col < 0 || col >= grid[0].length || 
           grid[row][col] == 0 || visited[row][col]) {
            return 0;
        }

        visited[row][col] = true;

        int area = 1;
        area += dfs(grid, visited, row + 1, col);
        area += dfs(grid, visited, row - 1, col);
        area += dfs(grid, visited, row, col + 1);
        area += dfs(grid, visited, row, col - 1);

        return area;
    }
}

The first solution is more space-efficient since it modifies the input grid to mark visited cells, while the second preserves the original grid using a separate visited array.