Leetcode 695. Max Area of Island

Problem Explanation:

This problem is about finding the maximum area of an island in a given 2D grid. The island is represented by 1's, and they must be connected 4-directionally (horizontal or vertical). The area of an island is the number of 1's in the group.

For example, given the grid below:

1
2
3[[0,0,1,0,0,0,0,1,0,0,0,0,0],
4 [0,0,0,0,0,0,0,1,1,1,0,0,0],
5 [0,1,1,0,1,0,0,0,0,0,0,0,0],
6 [0,1,0,0,1,1,0,0,1,0,1,0,0],
7 [0,1,0,0,1,1,0,0,1,1,1,0,0],
8 [0,0,0,0,0,0,0,0,0,0,1,0,0],
9 [0,0,0,0,0,0,0,1,1,1,0,0,0],
10 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

The maximum area of an island is 6.

Solution Walkthrough:

A Depth-First Search (DFS) can be performed to solve this problem. We can explore each cell in the grid. If the cell is 1, we then use DFS to visit all the connected cells (horizontally or vertically), count the number of cells visited, and mark these cells as visited by changing their value to 2. The maximum count of the cells visited during these processes will be the maximum area of an island.

Start with the first cell, if it's 0 move to the next cell. If it's 1, start a DFS and count all the connected cells.

1
2
3[0,0,1,0,0,0,0,1,0,0,0,0,0]    Start visiting from cell at index (0, 2)
4[0,0,0,0,0,0,0,1,1,1,0,0,0]    No options to move, the area is 1
5[0,1,1,0,1,0,0,0,0,0,0,0,0]
6[0,1,0,0,1,1,0,0,1,0,1,0,0]
7[0,1,0,0,1,1,0,0,1,1,1,0,0]
8[0,0,0,0,0,0,0,0,0,0,1,0,0]
9[0,0,0,0,0,0,0,1,1,1,0,0,0]
10[0,0,0,0,0,0,0,1,1,0,0,0,0]

Continue until all cells are visited. The maximum count across all the DFSs will be the maximum area.

Python Solution:

1
2python
3class Solution:
4    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
5        max_area = 0
6        for i in range(len(grid)):
7            for j in range(len(grid[0])):
8                max_area = max(max_area, self.dfs(grid, i, j))
9        return max_area
10
11    def dfs(self, grid: list[list[int]], i: int, j: int) -> int:
12        if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
13            return 0
14        if grid[i][j] != 1:
15            return 0
16        grid[i][j] = 2
17        return 1 + self.dfs(grid, i + 1, j) + self.dfs(grid, i - 1, j) + self.dfs(grid, i, j + 1) + self.dfs(grid, i, j - 1)

Java Solution:

1
2java
3public class Solution {
4    public int maxAreaOfIsland(int[][] grid) {
5        int maxArea = 0;
6        for(int i = 0; i < grid.length; i++) {
7            for(int j = 0; j < grid[0].length; j++)
8                maxArea = Math.max(maxArea, dfs(grid, i, j));
9        }
10        return maxArea;
11    }
12
13    private int dfs(int[][] grid, int i, int j) {
14        if(i < 0 || i == grid.length || j < 0 || j == grid[0].length)
15            return 0;
16        if(grid[i][j] != 1)
17            return 0;
18        grid[i][j] = 2;
19        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
20    }
21}

JavaScript Solution:

1
2js
3class Solution {
4    maxAreaOfIsland(grid) {
5    let maxArea = 0;
6        for (let i = 0; i < grid.length; i++) {
7            for (let j = 0; j < grid[0].length; j++) {
8                maxArea = Math.max(maxArea, this.dfs(grid, i, j));
9            }
10        }
11        return maxArea;
12    }
13
14    dfs(grid, i, j) {
15        if ( i < 0 || i === grid.length || j < 0 || j === grid[0].length) {
16            return 0;
17        }
18        if(grid[i][j] !== 1) {
19            return 0;
20        }
21
22        grid[i][j] = 2
23
24        return 1 + this.dfs(grid, i + 1, j) + this.dfs(grid, i - 1, j) + this.dfs(grid, i, j + 1) + this.dfs(grid, i, j - 1)
25    }
26}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int maxAreaOfIsland(vector<vector<int>>& grid) {
6        int max_area = 0;
7        for(int i=0; i< grid.size(); i++) {
8            for(int j=0; j<grid[0].size(); j++)
9                max_area = max(max_area, dfs(grid, i, j));
10        }
11        return max_area;
12    }
13   
14    int dfs(vector<vector<int>>& grid, int i, int j) {
15        if(i<0 || i == grid.size() || j<0 || j== grid[0].size())
16            return 0;
17        if(grid[i][j] != 1)
18            return 0;
19        grid[i][j] = 2;
20        return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) + dfs(grid, i, j+1) + dfs(grid, i, j-1);
21    }
22};

C# Solution:

1
2csharp
3public class Solution {
4    public int MaxAreaOfIsland(int[][] grid) {
5        int maxArea = 0;
6        for (int i = 0; i < grid.Length; i++) {
7            for (int j = 0; j < grid[0].Length; j++)
8                maxArea = Math.Max(maxArea, dfs(grid, i, j));
9        }
10        return maxArea;
11    }
12    
13    private int dfs(int[][] grid, int i, int j) {
14        if (i < 0 || i == grid.Length || j < 0 || j == grid[0].Length)
15            return 0;
16        if (grid[i][j] != 1)
17            return 0;
18        grid[i][j] = 2;
19        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
20    }
21}

For each language, the main approach is the same as explained. Start DFS on every cell containing 1, count the area and return the maximum of them.## Performance Comparison

The performance of the solution is almost identical across all languages. The only difference is that Python and JavaScript might be slightly slower due to them being interpreted languages, unlike Java, C++, and C#, which are compiled languages.

Space and Time Complexity

The space complexity of the solution is O(MN), where M is the number of rows in the grid, and N is the number of columns. This space is required to store the visited states of each cell in the grid.

The time complexity of the solution is also O(MN). In the worst-case scenario, we might need to visit every cell in the grid.

Optimizations

One possible optimization is reducing the space complexity by using a bit vector instead of an integer matrix to store the visited states of each cell. However, this might complicate the code and isn't likely to result in significant real-world performance improvement.

Conclusion

In implementing this solution, it is crucial to remember to update the state of a cell immediately after visiting it to avoid infinite recursion. Also, try to visualize the DFS process and how it explores the cells in the grid. This problem is a good opportunity to understand how Depth-First Search works in detail and its applications in solving real-world problems.

Overall, the presented solution in Python, JavaScript, Java, C++, and C# is efficient and straightforward, solving the problem by performing a Depth-First Search on the grid to find the maximum area of an island. The solution walkthrough and code snippets should provide a solid foundation for understanding and solving similar problems in the future.