695. Max Area of Island

Problem¶

Given a nonempty binary matrix, return the largest number of 1 cells in any island connected vertically or horizontally. Return 0 when there is no land.

Input:  [[1,1,0],
         [0,1,0],
         [1,0,1]]
Output: 3
Reason: The top island has 3 cells; diagonal cells are disconnected.

Key trick¶

Treat the matrix as an implicit graph: start a flood fill at each unvisited land cell, count its cells, and mark them as water immediately when discovered.

Trap¶

Counting diagonal neighbors as connected.
Marking cells only when removed from the stack, allowing duplicate insertions.
Forgetting that in-place marking mutates the input.
Using recursive DFS in Python when a large island could exceed the recursion limit.

Why is it interesting?¶

It is a compact application of graph traversal where the graph is represented implicitly by grid coordinates rather than adjacency lists.

Python solution¶

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

        def dfs(r, c):
            stack = [(r, c)]
            grid[r][c] = 0
            area = 0

            while stack:
                r, c = stack.pop()
                area += 1
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1):
                        grid[nr][nc] = 0
                        stack.append((nr, nc))

            return area

        best = 0

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))

        return best

Time complexity: \(O(mn)\).

Space complexity: \(O(mn)\) in the worst case for the explicit DFS stack.

Comment on my solution¶

Your solution is correct and interview-ready. The iterative DFS avoids recursion-depth failures, and marking neighbors before pushing them prevents duplicate visits.

Minor improvements:

Add parameter and return annotations to the nested function.
Use standard spacing after commas.
Increment the area when popping a cell, making the count directly correspond to processed cells.
Mention that the algorithm intentionally mutates grid; copy it first if callers require the input to remain unchanged.

# WORKS
class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = (-1,0), (1,0), (0,-1), (0,1)

        def dfs(r,c):
            stack = [(r,c)]
            grid[r][c] = 0 # flood fill
            area = 1

            while stack:
                r, c = stack.pop()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        area += 1
                        grid[nr][nc] = 0
                        stack.append((nr,nc))
            return area

        best = 0

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    best = max(best, dfs(r,c))
        return best