In this guide, you will get 695. Max Area of Island LeetCode Solution with the best time and space complexity. The solution to Max Area of Island problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Example 1:
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.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(1)
695. Max Area of Island LeetCode Solution in C++
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
ans = max(ans, dfs(grid, i, j));
return ans;
}
private:
int dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return 0;
if (grid[i][j] != 1)
return 0;
grid[i][j] = 2;
return 1 + //
dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + //
dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}
}; /* code provided by PROGIEZ */
695. Max Area of Island LeetCode Solution in Java
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int ans = 0;
for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
ans = Math.max(ans, dfs(grid, i, j));
return ans;
}
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return 0;
if (grid[i][j] != 1)
return 0;
grid[i][j] = 2;
return 1 + //
dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + //
dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}
} // code provided by PROGIEZ
695. Max Area of Island LeetCode Solution in Python
class Solution:
def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
def dfs(i: int, j: int) -> int:
if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
return 0
if grid[i][j] != 1:
return 0
grid[i][j] = 2
return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)
return max(dfs(i, j) for i in range(len(grid)) for j in range(len(grid[0]))) # code by PROGIEZ
