Leetcode: Max Area of Island

This question is asked at Facebook, Google, DoorDash, Amazon, and Microsoft, among others. It is an extremely common DFS (Depth-First Search) question that I will go over both the Iterative and recursive forms in this circumstance. It is as follows:

You are given an m x n binary matrix and an island is a group of 1's representing land connected either horizontally or vertically in 4 directions.  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, and if there is no island, return 0. The maximum area here is 6, with the blue indicating 0 and others indicating 1 which is an island. 

Example: 

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.

There are 2 ways to solve this problem. One is the recursive form. 

The intuition is that we want to know the area of each connected shape of the grid, then take the maximum of each of these. If we were on a land square and explore every square, we can add the total number of squares of that connected shape. We add 1 to the area of all the neighbors, if we see the neighbors exist. 

We will use seen to keep track of the squares that weren't visited in the past. 

class Solution {

    int[][] grid;

    boolean[][] seen; 

    public int area(int r, int c) {

        //see if things are within bound not seen and land. 

        if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || seen[r][c] || grid[r][c] == 0) return 0; 

        seen[r][c] = true;

        //else return the area based on that piece and the area of everywhere else. 

        return (1 + area(r + 1, c) + area(r - 1, c) + area(r, c - 1) + area(r, c + 1));

    }

    public int maxAreaOfIsland(int[][] grid) {

        this.grid = grid; 

        seen = new boolean[grid.length][grid[0].length]; 

        int ans = 0; 

        //return the maximum of the area. 

        for(int r = 0; r < grid.length; r++) {

            for(int c = 0; c < grid[0].length; c++) {

                ans = Math.max(ans, area(r, c));

            }

        }

    }

}

The next way to do this is through an iterative first search with a representation of all the directions. This is more complicated, but it's a good area to dive deep into. The seen items represent the squares that were either visited or added to the list. For every starting square that hasn't been visited we add other land square to the stack and keep count of number of squares seen and want to maximum of these counts, per land area. 

class Solution {

    public int maxAreaOfIsland(int[][] grid) {

        boolean[][] seen = new boolean[grid.length][grid[0].length]; 

        //all directions, row AND column 

        int[] dr = new int[]{1, -1, 0, 0};

        int[] dc = new int[]{0, 0, 1, -1};

        int ans = 0;

        //for all the rows and all of the columns 

        for(int r0 = ; r0 < grid.length; r0++) {

            for(int c0 = 0; c0 < grid[0].length; c0++) {

                //if this is land if not seen 

                if(grid[r0][c0] == 1 && !seen[r0][c0]) {

                    int shape = 0; 

                    //push the item to the stack

                    Stack<int[]> stack = new Stack(); 

                    stack.push(new int[]{r0, c0});

                    seen[r0][c0] = true; 

                    //while the stack is not empty

                    while(!stack.empty()) {

                        int[] node = stack.pop();     

                        int r = node[0], c = node[1]; 

                        shape++;

                        //for all directions

                        for(int k = 0; k < 4; k++) {

                            //all the row and the column

                            int nr = r + dr[k];

                            int nc = c + dc[k]; 

                            //if you are within bounds and not seen and land, then push the number

                            if(0 <= nr && nr < grid.length && 0 <= nc && nc < grid[0].length && grid[nr][nc] == 1 && !seen[nr][nc]) {

                            stack.push(new int[]{nr, nc})

                            seen[nr][nc] = true; 

                                        }

                        }

                    }

                    //find the biggest area of the shape

                    ans = Math.max(ans, shape);

                }

            }

        }

        //return the maximum area 

        return ans; 

    }

}

So then go through all the neighbors one by one and see if there's land and not visited and not seen.