0695. Max Area of Island

https://leetcode.com/problems/max-area-of-island

Description

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.

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.

ac

class Solution {
    int cnt = 0;
    int max = 0;
    public int maxAreaOfIsland(int[][] grid) {
        // edge cases
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    cnt = 0;
                    helper(grid, r, c);
                }
            }
        }

        return max;
    }

    private void helper(int[][] grid, int r, int c) {
        // exit
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
           || grid[r][c] == 0) {
            return;
        }

        grid[r][c] = 0; // mark visted
        cnt++;
        max = Math.max(max, cnt);

        // check neighbors
        helper(grid, r+1, c);
        helper(grid, r-1, c);
        helper(grid, r, c+1);
        helper(grid, r, c-1);
    }
}

Last updated

Was this helpful?