Problem Solving: Maximum Area of Island

Here is the link to the full description of the problem: Max Area of Island – LeetCode

The problem deals with a 2D array of values that are 0 or 1, and could even be true or false. If there is a 1 in the array, that is considered and island. If it’s a 0, then it’s water. The prompt is, “Given a random 2D array of values with islands and water, return the largest island’s size.” An island is only connected by adjacent spaces up, down, left, and right; note that it does not include diagonal connections.

This is a great problem, and I was able to solve it using a recursive function in which the algorithm is very lean. Here’s a brief and simple description of how to solve this: First, create a nested for loop that iterates through the x and y coordinates. We are searching the entire grid for a 1, and once we find a 1, then we run our recursive function, let’s call it int exploreIsland(int[][] tempGrid, int x, int y)

exploreIsland() works like this: Ask if you have found 1 unit of land at [x, y] in our tempGrid array that we enter as a parameter. If it is a hit (1), then mark it as a 0 so that you don’t redundantly look there again. Now we call our function recursively with all of the adjacent spaces. Contingent that our function does not access an element outside of the bounds of the array, we call exploreIsland(); on the space up, down, left, and right. It will keep expanding until it reaches the surrounding water around it, and it will keep tallying up the spaces of land that are there. After the method calls, if the area it returns is larger than the previous highest area, then it updates to the new highest area value. At the end of searching the entire grid, it will return the largest island’s area in the array.

Below is a gif of a model I made in Excel to show a visual representation of how the code works. We will be operating on the island in the middle. When an area is shaded, it means that it is calling the exploreIsland() method on that space next.

Here is the full code solution in Java:

class Solution
{
    public int maxAreaOfIsland(int[][] grid)
    {
        int maxSize = 0;
        for(int x = 0; x < grid.length; x++)
        {
            for(int y = 0; y < grid[x].length; y++)
            {
                if(grid[x][y] == 1)
                {
                    int temp = exploreIsland(grid, x, y);
                    if(temp > maxSize)
                        maxSize = temp;
                }
            }                
        }
        return maxSize;
    }
    
    public int exploreIsland(int[][] tempGrid, int x, int y)
    {
        int size = 1;
        tempGrid[x][y] = 0;
        if(x + 1 < tempGrid.length)
        {
            if(tempGrid[x + 1][y] == 1)
                size += exploreIsland(tempGrid, x + 1, y);
        }
        if(x - 1 >= 0)
        {
            if(tempGrid[x - 1][y] == 1)
                size += exploreIsland(tempGrid, x - 1, y);
        }
        if(y + 1 < tempGrid[x].length)
        {
            if(tempGrid[x][y + 1] == 1)
                size += exploreIsland(tempGrid, x, y + 1);
        }
        if(y - 1 >= 0)
        {
            if(tempGrid[x][y - 1] == 1)
                size += exploreIsland(tempGrid, x, y - 1);
        }
        return size;
    }
}

If you have any questions or comments, let me know below!