Algorithm Tutorial: Max Area of an Island (DFS)

For this entry in my algorithm walkthrough series, we will be looking at a 2D matrix search using a depth-first search approach.

We will first discuss the the problem, the solution, and then use a visualizer I created (and teased about in my last blog) to better understand the search process.

Contents

• Problem Description
• Problem Explanation
• Solution
  • Modeling the Solution

Problem Description

The specific problem we will be walking through, is problem Leetcode #695: Max Area of Island. The direct problem description found on Leetcode is:

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.

For example, the grid of:

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]]
}

Would return a value of 6, not 11, since the largest area of consecutive tiles in orthogonal directions is only 6, with the additional 5 tiles being connected diagonally, and thus considered a separate island. Leetcode provided this model to demonstrate the example:

Back to Top

Problem Explanation

If we were to perform this task mentally, the general approach would be to pick a starting point on an island, and then count each land tile that is connected to the current one, without repeating. If the island had different peninsulas or branches, we could count all of the land tiles in one peninsula before counting the rest of the tiles in the other.

This mental model is the exact process we can replicate with a depth first solution, previewed below:

In implementing this approach, we will need to:

• Iterate through the grid until we reach a "land tile".
  1. Count the tile and then somehow make note that we have visited this tile so that it doesn't get counted multiple times.
  2. Look at each orthogonal neighbor of that land tile to see if any of them are also land AND have not yet been visited.
  3. Add each unvisited land tile to the stack (a list of tiles we need check for additional neighbors)
  4. Repeat from step 2 by removing and using the most recently added item from the stack until there are no items remaining in the stack (meaning there are no more unvisited land tiles orthogonal to the current island)
• Once the first island is done being mapped, we update a maxArea variable to be whichever is greater: the result of the most recent island, or the previous value of maxArea.
• Continue iterating through the grid until we reach another land tile that has not already been visited, indicating a new island is present.

The second consideration that must be made, is how to keep track the land tiles that have already been visited:

• One answer would be to create a visited array, or object and add the coordinate pair for each land tile as it is counted. You would then need to check within this visited object to see if it already includes those coordinates. The advantages to this approach, are that it doesn't mutate the original grid, however more memory is going to be required for the function since we will be creating a new object.
• A second option, would be to change the value of land tile once it has been counted. In this problem, 1 denotes land. After a tile has been counted, we could change it to 0 (water) or any other value. As long as we are looking for 1's in the grid, these already visited tiles will not get re-used. This has the inverse effects from the previous solution, where we save space on a visited object, but the original grid will be mutated.

For my solution, I chose to mutate the grid, in particular because assigning different values based on a tiles "status" would allow me to model them different in a visualizer.

Back to Top

Solution

Using the pseudo-code in the previous section, we can implement the mapAreaOfIsland function in Javascript as shown below:

const maxAreaOfIsland = grid => {
  let maxArea = 0

  const mapIsland = (i, j) => {
    const stack = [[i, j]]
    let islandSize = 0
/*
These coordinates correspond to the four 
orthogonal changes from the current position
*/
    const directions = [[-1,0], [1,0], [0,1], [0,-1]]

    while (stack.length > 0){
      const tile = stack.pop()
      islandSize++
/*
For each of the four orthogonal directions, 
get the row and column index the change corresponds 
to and evaluate that tile.
*/
      for (const dir of directions){
        let nextRow = tile[0] + dir[0]
        let nextCol = tile[1] + dir[1]
        if ( grid[nextRow] && grid[nextRow][nextCol] && grid[nextRow][nextCol] === 1 ){
/*
If the tile is part of the grid, and its a land tile, 
we will change its value so that it doesn't get re-counted, and add these coordinates to the stack.
*/
          grid[nextRow][nextCol] = 3
          stack.push([nextRow, nextCol])
        }
      }
    }
    return islandSize
  }

  for (let i = 0; i < grid.length; i++){
    for (let j = 0; j < grid[0].length; j++){
      if (grid[i][j] === 1){
/* 
We found the starting point for our island, mark this point as visited, 
and then begin scanning the island. 
The returned size will be compared to the current maxArea to 
determine which is greater and update the value of maxArea if needed.
*/
        grid[i][j] = 3
        maxArea = Math.max(maxArea, mapIsland(i, j))
      }
    }
  }
  return maxArea
};

Modeling the Solution

For myself, it often helps to have a visual model of a process that illustrates the steps that are occurring. To further my own understanding, and to hopefully help you, I created a visualizer using CodeSandbox To help model the depth first search.

In this visualizer, the solution implementation above was modified so that the current state of the tile: unvisited land, unvisited water, visited land, visited water, andpending (in the stack) was denoted by different numerical values. As the state of the tile changed throughout the function, the value was updated leading to a visual change in the styling. Here is a preview of the search for the initial example grid:

Other modifications to the solution that were needed to produce the visualizer included cloning the grid after each mutation in order to update the component state and re-render the component. The sleep() function described in my last blog allows us also to purposely slow down the solution in order to perceive and follow the search pattern. If you would like to change the speed of the visualizer, you can adjust the {sleep: } option argument on line 31 where the custom hook is invoked.

Aside from the three pre-defined grids, I also added acreate a custom map feature to create different scenarios to run the search on. Enter the number of rows/columns you'd like, and then click a tile to toggle it as land or water. After selecting "Use this map" you can search against this one shown below: