Max Area of Island medium

Problem Statement

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.

Find the maximum area of an island in the given grid. 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 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,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

Steps

1. Initialization: Create a visited matrix of the same size as grid to keep track of visited cells. Initialize it with all false values.

2. Iterate: Traverse the grid. For each cell grid[i][j], if it's a 1 (land) and hasn't been visited, call a Depth-First Search (DFS) function to explore the island.

3. Depth-First Search (DFS): The DFS function takes the row and column index as input. It recursively explores all connected land cells (4-directionally) and counts them.

4. Update Maximum Area: After each DFS call, update the max_area variable if the current island area is larger.

5. Return Maximum Area: After traversing the entire grid, return max_area.

Explanation

The solution uses Depth-First Search (DFS) to explore connected components (islands) in the grid. The visited matrix prevents revisiting cells and ensures that we correctly count the area of each island. The DFS function recursively explores adjacent land cells, adding to the area count as it goes. The algorithm efficiently finds the maximum area by exploring each island only once.

Code

#include <vector>

using namespace std;

int dfs(vector<vector<int>>& grid, int r, int c, vector<vector<bool>>& visited) {
    int rows = grid.size();
    int cols = grid[0].size();

    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(grid, r + 1, c, visited) + dfs(grid, r - 1, c, visited) +
           dfs(grid, r, c + 1, visited) + dfs(grid, r, c - 1, visited);
}

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int rows = grid.size();
    if (rows == 0) return 0;
    int cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int max_area = 0;

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

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. We visit each cell at most once.
• Space Complexity: O(M * N) in the worst case, due to the visited matrix. In the best case, the space complexity is O(max(M,N)), depending on the island size and the depth of the recursive calls within the DFS function. The call stack during DFS can potentially reach a depth proportional to the maximum dimension of the grid.