Solution Developed In:

The Question

For this article we will be covering Leetcode's '695. Max Area of Island' question. Which is the successor of 200. Number of Islands questions. Their solutions are very similar.

Question:

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

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.

Explaining The Question

This Question is rated Medium. Which is for the most part accurate. But this is ONLY Medium if you have a good grasp of Depth First Search or Breadth First Search on Graph Theory. Ideally a solid understanding of the Adjacency List and Adjacency Matrix will be helpful.

What we're dealing with here is a Graph with Nodes and Edges which are represented by a M x N 2D Array. Where the relationship between the nodes are by the edges that connect them. That's to say a nodes neighbors are the nodes that are adjacent to it. Meaning, left, right, top, and bottom are the neighbors.

We need to traverse this Graph and find each island. At each island we make a count, 'How many cells are in the island'? Once we get the number of known cells in the island we ask again 'Is this the largest island we have seen so far?' If it is, we update the largest island count.

Recommended Knowledge

1. Graph Theory
2. Adjacency List
3. Adjacency Matrix
4. Depth First Search

What do we know?

1. We have a 2D Array of '1's and '0's.
2. It's a M x N Matrix
3. Neighbors are left, right, top, and bottom.
4. We need to find the max area of an island. Meaning, the number of cells in the island.

How we're going to do it:

What we're going to do is traverse each node in the Graph and at each node we're going to check if it's a land or water. In the case of land we're going to perform a Depth First Search. Where we will traverse the entire island all together. When we detect this island, we start a counter which will increment by 1 at each node we visit in the island. Once the Depth First Search is complete, we will check if the counter is the largest we've seen so far. If it is, we'll update the largest island count.

We prevent re-visiting each island by making each cell in the island a '0'. We're turning land into water. 😁

1. We're going to declare a global variable called max_island_area which will keep track of the largest island area we've seen so far.
2. We're going to visit every node in the matrix, by iterating through each row and each column.
3. At each node we ask if it's a land or water. 1 or 0. If 0, we've either already visited it / just water.
4. If 1, we've found un-explored land and we need to traverse that entire island.
5. We perform a Recursive Depth First Search on that island. Where we start a counter. Where we ask recursively if the node above, below, left and right is a 1 or not? If any of those are 1, we visit it and continue the DFS until we have exhausted the island. Each cell we visit increments this counter
6. Now the island is fully explored we know the number of cells in the island. We check if this counter is the largest we've seen so far. If it is, we update the largest island area.
7. Repeat until we've exhausted the matrix.

Big O Notation:

• Time Complexity: O(V * E) / O(n) | Where n is the number of nodes in the Matrix. As we're going to visit every node in the matrix. Where V is the number of nodes in the graph and E is the number of edges in the graph. As in the worst case, we will visit each node and each one of it's vertexes, which would mean the entire matrix is an island.
• Space Complexity: O(h) | Where h is the largest number of nodes within a island, as we will store all of those nodes within the Call Stack to perform our Depth First Search.

The Big O Notation analysis for this problem is a little confusing as it combines a handful of different concepts all with their own Big O Notations. But in general, we reduce it down to the worst complexity being O(n). Feel free to correct me if you feel my analysis is wrong.

Leetcode Results:

See Submission Link:

• Runtime: 78 ms, faster than 85.83% of JavaScript online submissions for Max Area of Island
• Memory Usage: 45.1 MB, less than 67.24% of JavaScript online submissions for Max Area of Island.

The Solution

var maxAreaOfIsland = function (grid) {

    // This is just a cute little shorthand for the grid.
    // Makes reading the code easier. :D 
    // Also it's memoization 😁 
    const max_row_length = grid[0].length - 1;
    const max_grid_height = grid.length - 1;

    // The max area will be the largest counter we will find.
    // Our counter will count the number of nodes within any given island
    // resting on each new island. 
    let max_island_area = 0;
    let island_node_counter = 0;

    // Depth First Search on the Matrix
    const explore_island_DFS = (row_index, col_index) => {

        // Firstly, validation
        // Is the given idex out of bounds?
        if (row_index > max_grid_height || col_index > max_row_length || row_index < 0 || col_index < 0) {
            // Grossly invalid
            return 0;
        }

        // Valid island?
        if (grid[row_index][col_index] === 0) {
            return 0;
        }

        // Destroy island
        grid[row_index][col_index] = 0;

        // Explore islands incrementing the island_node_counter
        island_node_counter += 1;

        // X being our current node
        //    ^
        // <  x  >
        //    v
        explore_island_DFS(row_index - 1, col_index); // Up
        explore_island_DFS(row_index + 1, col_index); // Down
        explore_island_DFS(row_index, col_index - 1); // Left
        explore_island_DFS(row_index, col_index + 1); // Right

        // Now we've explored all of our neighbors,
        // we should have a counter of the number of nodes within this island.
        // Is it greater than our current max?
        max_island_area = Math.max(island_node_counter, max_island_area);
    };

    // Iterate over the grid.
    grid.forEach((row, row_index) => {
        row.forEach((col, col_index) => {

            // We found an island.
            if (col === 1) {
                // Traverse this entire island.
                // and remove it while iterating through
                // incrementing it's island_node_counter and cross checking it with the
                // max area.
                island_node_counter = 0; // This will be the number of nodes in this island.
                explore_island_DFS(row_index, col_index);
            }
        });
    });

    return max_island_area;
};