Max Area of Island

Medium Problem 100 of 151 Java and Python

Problem

You are given an m × n binary matrix grid, where 1 is land and 0 is water. An island is a group of 1s connected horizontally or vertically.

Return the area (number of cells) of the largest island, or 0 if there is none.

Example 1

Input: grid = [[0, 1, 1], [0, 1, 0], [1, 0, 1]]
Output: 3
Why: The top island has 3 cells; the others have 1.

Example 2

Input: grid = [[0, 0, 0]]
Output: 0

Constraints

1 ≤ m, n ≤ 50

Explanation

This is Number of Islands where each flood fill also counts the cells it sinks. Make the DFS return 1 + area of the four neighbours.

Approach 1 · Better

BFS with a counter

Time O(m · n)
Space O(m · n)

For each new island, BFS through it, counting cells, and keep the maximum.

For each land cell: set it to 0, start a queue and area = 0.
Pop cells, incrementing area, and enqueue land neighbours (marking them 0).
Update the best area.

Java

import java.util.*;

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        int best = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) {
                    continue;
                }
                grid[i][j] = 0;
                Deque<int[]> queue = new ArrayDeque<>();
                queue.add(new int[] { i, j });
                int area = 0;
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    area++;
                    for (int[] d : dirs) {
                        int r = cell[0] + d[0];
                        int c = cell[1] + d[1];
                        if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] == 1) {
                            grid[r][c] = 0;
                            queue.add(new int[] { r, c });
                        }
                    }
                }
                best = Math.max(best, area);
            }
        }
        return best;
    }
}

Python

from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        best = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1:
                    continue
                grid[i][j] = 0
                queue, area = deque([(i, j)]), 0
                while queue:
                    r, c = queue.popleft()
                    area += 1
                    for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                            grid[nr][nc] = 0
                            queue.append((nr, nc))
                best = max(best, area)
        return best

Approach 2 · Optimal

DFS returning the area

Time O(m · n)
Space O(m · n) recursion worst case

A recursive DFS returns how many land cells it sank.

area(r, c): 0 if out of bounds or water.
Otherwise set the cell to 0 and return 1 + area of the four neighbours.
Take the maximum over all starting cells.

Java

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                best = Math.max(best, area(grid, i, j));
            }
        }
        return best;
    }

    private int area(int[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != 1) {
            return 0;
        }
        grid[r][c] = 0;
        return 1 + area(grid, r + 1, c) + area(grid, r - 1, c) + area(grid, r, c + 1) + area(grid, r, c - 1);
    }
}

Python

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def area(r, c):
            if not (0 <= r < m and 0 <= c < n) or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1)

        return max(area(i, j) for i in range(m) for j in range(n))

Complexity compared

Approach	Time	Space
Better BFS with a counter	O(m · n)	O(m · n)
Optimal DFS returning the area	O(m · n)	O(m · n) recursion worst case

Key takeaways

Let a DFS return something (a count, a sum, a boolean) to answer questions about each component.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem