# [Leetcode] 695. Max Area of Island

limelimejiwon·2022년 3월 14일
0

## Python으로 공부하는 코딩테스트

목록 보기
15/67 ## 📄 Description

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

## 🔨 My Solution

1. Go through every square and check if the current square is island.
2. If it is an island, area+1 and check the adjacent squares also.
3. The pixel should be valid one.
4. when the dfs is over,
• update the max_area variable by comparing with area variable
• area variable should be reset to 0
5. repeat this process through DFS.

## 💻 My Submission

class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
R,C=len(grid),len(grid)
self.area=max_area=0
check=[[False]*C for _ in range(R)]

def dfs(r,c):
check[r][c]=True
if grid[r][c]==1:
self.area+=1
if c+1<C and not check[r][c+1]: dfs(r,c+1)
if r+1<R and not check[r+1][c]: dfs(r+1,c)
if c-1>=0 and not check[r][c-1]: dfs(r,c-1)
if r-1>=0 and not check[r-1][c]: dfs(r-1,c)

for i in range(R):
for j in range(C):
dfs(i,j)
if max_area<self.area:
max_area=self.area
#print(f"max area",max_area)
self.area=0
return max_area

## 🔎 Complexity

Time Complexity: O(M*N)
M is the number of rows, and N is the number of colums.
We visit every square once.
Space Complexity:O(R*C)
the space used by check to keep track of visited squares, and the space used by the call stack during our recursion.

## 💡 What I learned

1. There are multiple ways to avoid using the global variable, the first solution is to use class or nested function (pseudocode):
global area

to

self.area=0