# 695. Max Area of Island

###### tags: `leetcode` `DFS` `695` `medium` `google`

## Question

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`.

Return the number of connected components in the graph.

### 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

Constraints:

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 50`
* `grid[i][j] is either 0 or 1.`

## My first solution

* :medal: **思考一**:一看到什麼 island 的題目，要你找最大最小面積，直接往 dfs 去想
* :medal: **思考二**:把每一個點都走遍當發現你當下走的路是有島嶼的那就再往四個方向繼續走走到沒有島嶼，然後走到沒有路可以走了就把目前走到的島嶼面積記錄下來。
* :medal: **思考三**:我必須要有一個 visited 去檢視我有走過的點，有走過就不走了。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        self.m = len(grid)
        self.n = len(grid[0])
        self.visited = [[0] * self.n for i in range(self.m) ]
        ans = 0
        
        # 全部 matrix的值 都走一遍         
        for x in range(self.m):
            for y in range(self.n):
                self.count = 0
                self.dfs(grid, x, y)
                self.visited[x][y] = 1
                ans = max(ans, self.count)    
        
        return ans 
    
    def dfs(self, grid , x, y):
        # 檢視 x y 有沒有超出 matrix 的範圍         
        if x >= 0 and x < self.m and y >= 0 and y < self.n and grid[x][y] == 1 and not self.visited[x][y]:
            self.count += 1
            self.visited[x][y] = 1
            
            # 往四個方向走             
            self.dfs(grid, x+1, y)
            self.dfs(grid, x-1, y)
            self.dfs(grid, x, y+1)
            self.dfs(grid, x, y-1)

## :memo: bigO
* 時間複雜度: m*n (matrix的每個值都看過一遍)
* 空間複雜度: m*n (visited matrix)

## :-1: **檢討**
* 看 code 有沒有更好的寫法會讓我的速度會快一點，因為我看別人的解法也都是 Big(O)= m*n。
* 這題解題思路蠻簡單的，但code要寫出來要思考一下。
* 我應該在程式10.11行這邊做一個判斷 `if grid[x][y]:` 然後才往下做，加上後速度果然有提升。

## :memo: My first solution FIX

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        self.m = len(grid)
        self.n = len(grid[0])
        self.visited = [[0] * self.n for i in range(self.m) ]
        ans = 0
        
        # 全部 matrix的值 都走一遍         
        for x in range(self.m):
            for y in range(self.n):
                if grid[x][y]:
                    self.count = 0
                    self.dfs(grid, x, y)
                    self.visited[x][y] = 1
                    ans = max(ans, self.count)    

        return ans 
    
    def dfs(self, grid , x, y):
        # 檢視 x y 有沒有超出 matrix 的範圍         
        if x >= 0 and x < self.m and y >= 0 and y < self.n and grid[x][y] == 1 and not self.visited[x][y]:
            self.count += 1
            self.visited[x][y] = 1
            
            # 往四個方向走             
            self.dfs(grid, x+1, y)
            self.dfs(grid, x-1, y)
            self.dfs(grid, x, y+1)
            self.dfs(grid, x, y-1)

## :memo: leetcode solution

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
            seen = set()
            def area(r, c):
                if not (0 <= r < len(grid) and 0 <= c < len(grid[0])
                        and (r, c) not in seen and grid[r][c]):
                    return 0
                seen.add((r, c))
                return (1 + area(r+1, c) + area(r-1, c) +
                        area(r, c-1) + area(r, c+1))

            return max(area(r, c)
                       for r in range(len(grid))
                       for c in range(len(grid[0])))

## :memo: bigO
* 時間複雜度: m*n (matrix的每個值都看過一遍)
* 空間複雜度: m*n (visited matrix)

## :memo: 討論
* 我覺得第二種寫法就速度上比較快一點點，且程式比較簡潔，但我覺得如果是白板題，我可能會比較直覺地用我原本的寫法。