Matrix: LeetCode Problem 695 Walkthrough(Part 3)

695. Max Area of Island: This problem is a little trickier than the previous ones, as we will be using recursion. We are asked to find the largest “island” (or set of connecting 1s).

Problem 659

695 Solution

Step by step:

1. Initiate the count variable to track the largest island
2. Iterate through every item in each row of the array.
3. Once you find an “island” (grid[i][j] === 1) use the helper function (defs(i,j))
4. Here we are using recursion so our base case will be if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === 0 )return 0. Simply saying that if the point does not exist (gone off the gird) or if the point is not an island (===1) then we return 0 and stop our recursion for that point.
5. Next we remove the island (grid[x][y]). This prevents us from double counting, and makes sure that once we found all islands we will hit our base case (all points will be 0).
6. Finally we put it all together, by adding a variable area. In this variable we are recursively calling our DFS function. We are performing Depth-first search on each side of the element. Returning the area of that island to the variable count = Math.max(count, dfs(i,j)).

• Example: We set the element equal to zero, then check the top if nothing is there we return zero. Next we check the bottom if we found a one we check that elements top, bottom, left, and right (we do not move to the next side until the current side returns a zero… base case)

7. Once we are done iterating we will return the max count (return count).

Max Area of Island — LeetCode