Max Area of Island medium

Problem Statement

Given a grid representing a map where 0 represents water and 1 represents land, find the maximum area of an island (i.e., a connected group of 1s). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1

Input: grid = [[0,0,1,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0]] Output: 1 Explanation: The only island consists of one land cell.

Example 2

Input: grid = [[0,0,1,0,0],[0,0,1,0,0],[0,0,1,0,0],[0,0,0,0,0]] Output: 3 Explanation: The largest island has 3 land cells.

Steps to Solve

1. Depth-First Search (DFS): We'll use DFS to traverse each connected component of land cells. DFS is ideal for exploring connected graphs or, in this case, connected components within a grid.

2. Island Area Calculation: Each time we encounter a land cell (1), we initiate a DFS traversal starting from that cell. During the traversal, we count the number of land cells visited (this represents the area of the island).

3. Maximum Area Tracking: We keep track of the maximum island area encountered so far.

4. Visited Matrix: To prevent revisiting already explored land cells, we use a visited matrix of the same size as the input grid. This matrix keeps track of which cells have already been explored.

Explanation

The algorithm iterates through each cell in the grid. If a cell contains land (1) and hasn't been visited, we start a DFS traversal. The DFS recursively explores adjacent land cells, incrementing the area counter for each visited cell and marking them as visited in the visited matrix. After the DFS completes for a particular island, we update the maxArea if the current island's area is larger.

Code (Java)

class Solution {
    int rows, cols;
    int[][] grid;
    boolean[][] visited;

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

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

    private int dfs(int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0 || visited[r][c]) {
            return 0;
        }
        visited[r][c] = true;
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
    }
}

Complexity Analysis

• Time Complexity: O(M * N), where M and N are the number of rows and columns in the grid, respectively. In the worst-case scenario, we visit each cell once.
• Space Complexity: O(M * N) in the worst case due to the visited matrix. The recursion depth of DFS is at most M + N (diameter of the grid), but the space usage is dominated by the visited matrix.