Leetcode 695. Max Area of Island

Problem

Leetcode 695 - Max Area of Island

Example:

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.

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Approach

Similar to the Leetcode-200 question, we can use DFS to check valid land.

We can update the res every time we’re on valid land during DFS

Here is the Python code for the solution:

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        res = 0

        def dfs(i, j):
            nonlocal area
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
                return area
            
            print(area)
            grid[i][j] = 0
            area += 1
            dfs(i+1, j)  
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
            return area

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    continue
                print(res)
                area = 0
                res = max(res, dfs(i, j))
        
        return res  

Time Complexity and Space Complexity

Time Complexity: $O(n * m)$

Space Complexity: $O(n * m)$