Max Area of Island - Video Solutions

Problem Overview: You get an m x n binary grid where 1 represents land and 0 represents water. An island is a group of connected land cells (4-directionally). The task is to compute the maximum number of cells in any island.

Approach 1: Depth First Search (DFS) Flood Fill (O(m*n) time, O(m*n) space)

Scan the grid and start a DFS whenever you encounter an unvisited land cell. The DFS recursively explores all 4 directions (up, down, left, right) and counts how many cells belong to that island. Mark each visited cell as 0 or store it in a visited set so it is not counted again. Each cell is processed once, so the traversal cost is linear in the grid size. DFS is simple to implement and fits naturally with recursion when solving Depth-First Search problems on a matrix.

Approach 2: Breadth First Search (BFS) Traversal (O(m*n) time, O(m*n) space)

BFS solves the same flood-fill problem using a queue instead of recursion. When a land cell is found, push it into a queue and repeatedly process neighbors while counting the island size. Each step dequeues a cell, checks the four directions, and enqueues any unvisited land cells. BFS avoids recursion depth issues and can be easier to reason about in iterative environments. This approach is common in grid traversal questions involving Breadth-First Search.

Approach 3: Union Find (Disjoint Set) (O(m*n α(n)) time, O(m*n) space)

Union Find treats every land cell as a node in a disjoint-set structure. As you iterate through the grid, union adjacent land cells into the same set. Maintain a size array that tracks how many cells belong to each component. The maximum component size becomes the largest island. Path compression and union by rank keep operations near constant time. This approach is useful when you already model the grid as connected components using Union Find, though it is more complex than DFS or BFS.

Recommended for interviews: DFS or BFS flood fill is the expected solution. Both run in O(m*n) time because every cell is visited at most once. DFS is slightly shorter to write in most languages, while BFS avoids recursion limits. Interviewers typically want to see correct grid traversal, boundary checks, and visited marking. Union Find demonstrates deeper graph modeling but is rarely necessary for this problem.