[Leetcode] 695. Max Area of Island

📄 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[0])
        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

References
https://leetcode.com/problems/max-area-of-island/
https://windsooon.github.io/2019/08/23/How%20to%20use%20global%20variables%20correctly/