This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #695 (Medium): Max Area of Island
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
You are given an
m x nbinary matrix grid. An island is a group of1'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
1in the island.Return the maximum area of an island in grid. If there is no island, return
0.
Examples:
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. Visual:
Example 2: Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
So we can just use a simple iteration through the grid and look for islands. When we find an island, we can use a recursive helper function (trav) to sum up all the connected pieces of land and return the total land mass of the island.
As we traverse over the island, we can replace the 1s with 0s to prevent "finding" the same land twice. We can also keep track of the largest island found so far (ans), and after the grid has been fully traversed, we can return ans.
- Time Complexity: O(N * M) where N and M are the lengths of the sides of the grid
-
Space Complexity: O(L) where L is the size of the largest island, representing the maximum recursion stack
- or O(N * M + L) if we create an N * M matrix in order to not modify the input
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var maxAreaOfIsland = function(grid) {
let ans = 0, n = grid.length, m = grid[0].length
const trav = (i, j) => {
if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0
grid[i][j] = 0
return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
}
for (let i = 0; i < n; i++)
for (let j = 0; j < m; j++)
if (grid[i][j]) ans = Math.max(ans, trav(i, j))
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans, n, m = 0, len(grid), len(grid[0])
def trav(i: int, j: int) -> int:
if i < 0 or j < 0 or i >= n or j >= m or grid[i][j] == 0: return 0
grid[i][j] = 0
return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
for i, j in product(range(n), range(m)):
if grid[i][j]: ans = max(ans, trav(i, j))
return ans
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
private int n, m;
public int maxAreaOfIsland(int[][] grid) {
int ans = 0;
n = grid.length;
m = grid[0].length;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j] > 0) ans = Math.max(ans, trav(i, j, grid));
return ans;
}
private int trav(int i, int j, int[][] grid) {
if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] < 1) return 0;
grid[i][j] = 0;
return 1 + trav(i-1, j, grid) + trav(i, j-1, grid) + trav(i+1, j, grid) + trav(i, j+1, grid);
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
n = grid.size(), m = grid[0].size();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j]) ans = max(ans, trav(i, j, grid));
return ans;
}
private:
int n, m;
int trav(int i, int j, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0;
grid[i][j] = 0;
return 1 + trav(i-1, j, grid) + trav(i, j-1, grid) + trav(i+1, j, grid) + trav(i, j+1, grid);
}
};
Top comments (0)