Max Area of Island

NeetCode: Max Area of Island · LeetCode: 695. Max Area of Island · Difficulty: Medium

Given an m x n binary grid, return the area (number of cells) of the largest island, where an island is a group of 1s connected horizontally or vertically. If there is no island, return 0.

Example

Text

grid:  0110     Output: 5
       1100
       0011
       0111

The top-left island has 4 cells and the bottom-right one has 5.

Brute force: flood fill from every land cell

For each land cell, measure the island containing it with a fresh visited matrix, and keep the maximum. An island of k cells is measured k times, and each measurement allocates a new visited matrix. The flood fill uses an ArrayDeque<int[]> of {row, column} pairs as a stack.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private int islandSize(int[][] grid, int sr, int sc) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        visited[sr][sc] = true;
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{sr, sc});
        int size = 0;
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            size++;
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0];
                int nc = cell[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
                    continue;
                }
                if (grid[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    stack.push(new int[]{nr, nc});
                }
            }
        }
        return size;
    }

    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[r].length; c++) {
                if (grid[r][c] == 1) {
                    best = Math.max(best, islandSize(grid, r, c));
                }
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] grid = {
            {0, 1, 1, 0},
            {1, 1, 0, 0},
            {0, 0, 1, 1},
            {0, 1, 1, 1},
        };
        System.out.println(s.maxAreaOfIsland(grid));
        System.out.println(s.maxAreaOfIsland(new int[][]{{0, 0, 0}}));
        System.out.println(s.maxAreaOfIsland(new int[][]{}));
    }
}

Output

5
0
0

Time: O((m * n)^2) worst case, e.g. an all-land grid runs a full fill from each of the m * n cells. Space: O(m * n).

Optimal: one flood fill per island

Once a cell has been counted as part of an island, no other start cell in that island needs to be tried. So sink each land cell (set it to 0) as it is pushed on the stack, and count how many cells one fill sinks. The area of every island is measured exactly once, and the answer is the largest count. This is the sink-in-place approach of Number of Islands with a counter added. It overwrites the input grid, which LeetCode allows.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int best = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != 1) {
                    continue;
                }
                grid[r][c] = 0;
                Deque<int[]> stack = new ArrayDeque<>();
                stack.push(new int[]{r, c});
                int area = 0;
                while (!stack.isEmpty()) {
                    int[] cell = stack.pop();
                    area++;
                    for (int[] d : DIRS) {
                        int nr = cell[0] + d[0];
                        int nc = cell[1] + d[1];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
                            continue;
                        }
                        if (grid[nr][nc] == 1) {
                            grid[nr][nc] = 0;
                            stack.push(new int[]{nr, nc});
                        }
                    }
                }
                best = Math.max(best, area);
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] grid = {
            {0, 1, 1, 0},
            {1, 1, 0, 0},
            {0, 0, 1, 1},
            {0, 1, 1, 1},
        };
        System.out.println(s.maxAreaOfIsland(grid));
        System.out.println(s.maxAreaOfIsland(new int[][]{{0, 0, 0}}));
        System.out.println(s.maxAreaOfIsland(new int[][]{}));
    }
}

Output

5
0
0

Time: O(m * n). Space: O(m * n) worst case for the stack.