695. Max Area of Island
## description
## 695. Max Area of Island
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:
1Input: 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]]
2Output: 6
3Explanation: The answer is not 11, because the island must be connected 4-directionally.Example 2:
1Input: grid = [[0,0,0,0,0,0,0,0]]
2Output: 0- –m == grid.length
- –n == grid[i].length
- –1 <= m, n <= 50
- –grid[i][j] is either 0 or 1.
Constraints:
## notes
### Intuition
Calculate the area for each island when it is seen and mark that island as visited.
### Implementation
We can iterate over each node in the grid and if it is a 1, we use DFS to calculate the area for that island and mark all those nodes as visited at the same time to avoid double counting.
For the DFS function, our base case is when the node is not a 1, we return 0 as the area then. Otherwise, we mark that node as visited by setting it to 0 and start our count at 1. Then, we iterate over all the neighbours of the node (provided they are in bounds), and add the result for the recursive call to our count. Finally, we return the count.
- –Time: O(m * n), in the worst case, the whole grid is an island so we will DFS through the whole grid in the first iteration and then never again.
- –Space: O(m * n), recursive call stack.
### Complexity
## solution
1from typing import List, Tuple
2
3class Solution:
4 def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
5 n = len(grid)
6 m = len(grid[0])
7
8 def neighbs(i: int, j: int) -> List[Tuple[int, int]]:
9 res = []
10 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
11
12 for di, dj in dirs:
13 ni, nj = i + di, j + dj
14 if ni < 0 or ni >= n or nj < 0 or nj >= m:
15 continue
16 res.append((ni, nj))
17
18 return res
19
20 def dfs(i: int, j: int) -> int:
21 if grid[i][j] != 1:
22 return 0
23 grid[i][j] = 0
24 curr = 1
25 for ni, nj in neighbs(i, j):
26 curr += dfs(ni, nj)
27 return curr
28
29 max_area = 0
30 for i in range(n):
31 for j in range(m):
32 if grid[i][j] == 1:
33 max_area = max(max_area, dfs(i, j))
34 return max_area
35
36
37
38
39if __name__ == "__main__":
40 # Include one-off tests here or debugging logic that can be run by running this file
41 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
42 solution = Solution()
43