Skip to content
AI360Xpert
Back to Graphs
Medium

Max Area of Island

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. The area of an island is the number of cells with a value `1` in the island. Return the maximum area of an island in `grid`. If there is no island, return `0`.

Examples

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
The answer is not 11, because the island must be connected 4-directionally.
Input:grid = [[0,0,0,0,0,0,0,0]]
Output:0
There are no islands in the grid, so the maximum area is 0.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

Depth-First Search (DFS)

Approach

This problem is very similar to "Number of Islands". We iterate through each cell. When we find a `1`, we start a DFS to find the area of the island. The DFS function returns the area of the connected component starting from the given cell. It marks the cell as visited (e.g., changing `1` to `0`) and adds 1 for the current cell, plus the area returned by recursively calling DFS on its 4 neighbors. We keep track of the maximum area found so far across all DFS calls.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

Time complexity is O(m * n) because we visit each cell at most a constant number of times. Space complexity is O(m * n) in the worst case for the recursion stack if the grid is filled with lands.

Solution.java
class Solution {    public int maxAreaOfIsland(int[][] grid) {        if (grid == null || grid.length == 0) {            return 0;        }                int maxArea = 0;        int m = grid.length;        int n = grid[0].length;                for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    maxArea = Math.max(maxArea, dfs(grid, i, j));                }            }        }                return maxArea;    }        private int dfs(int[][] grid, int r, int c) {        int m = grid.length;        int n = grid[0].length;                // Out of bounds or water        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == 0) {            return 0;        }                // Mark as visited        grid[r][c] = 0;                // Current cell (1) + area of 4 neighbors        return 1 + dfs(grid, r + 1, c) +                   dfs(grid, r - 1, c) +                   dfs(grid, r, c + 1) +                   dfs(grid, r, c - 1);    }}