0695.Max Area of Island

Link: 695. Max Area of Island - Medium
Track: NeetCode150

Question

Restate the problem

• Given a 2d grid, with 0 and 1. 1 is land, 0 is water.
• An island is connected 4-directionally (up/down/left/right).
• Return the maximum number of land cells in any island.

Edge Case

• If there is no grid, return 0

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	BFS (visited set)	$O(m\cdot n)$	$O(m\cdot n)$

Method 1 - BFS (visited set)

Key idea:

• Each land cell is added to the queue at most once.
• BFS visits exactly the connected components, so the counted size is exactly the island’s area.
  BFS 会完整遍历一个连通块（一个岛屿的所有相连陆地），因此统计到的 size 就是该岛屿的面积。

Key Approach

• Scan every cell
• When I find a land cell that has not been visited, that cell must be the start of a new island, so I run BFS from it to compute its area.
• During the BFS, I expand to 4 neighbors. If a neighbor is in-bounds, is land, and unvisited, I mark it visited and push it into the queue.
• The BFS returns the island’s area, and I update the global maximum.

Complexity

• Time Complexity: $O(m\cdot n)$
• Space Complexity: $O(m\cdot n)$

Code

from collections import deque
 
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
	        return 0
            
        rows, cols = len(grid), len(grid[0])
        visited = set()
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        res = 0
        def bfs(r, c):
            if not grid or not grid[0]:
                return 0
 
            queue = deque([(r, c)])
            visited.add((r, c))
            size = 1
            while queue:
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if (
                        (0 <= nr < rows and 0 <= nc < cols) and
                        grid[nr][nc] == 1 and
                        (nr, nc) not in visited
                    ):
                        size += 1
                        queue.append((nr, nc))
                        visited.add((nr, nc))
            return size
 
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and (r, c) not in visited:
                    max_area = bfs(r, c)
                    res = max(res, max_area)
        
        return res

---

Mistake

• Type pitfall use int 1 not str "1".