## DEV Community 👩‍💻👨‍💻 is a community of 932,977 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 695. Max Area of Island 🚀

### 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.

## 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:

• 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.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;
};

``````