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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.