Skip to main content
Talentd

Max Area of Island - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchUnion Find19 min readAsked at: Amazon, Microsoft, Apple +17
Practice this problem

Problem Statement

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.

 

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.

Example 2:

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

 

Constraints:

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

Approach Overview

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.

Approach 1: Depth First Search (DFS) Approach

In this approach, we will use Depth First Search (DFS) to explore the grid. The idea is to iterate over each cell in the grid and apply DFS when we encounter an unvisited cell that is a part of an island (i.e., grid value is 1). We will mark each visited cell to avoid revisiting. By keeping a count of the size of each island found, we can track the maximum size encountered.

This C solution defines a DFS function that recursively counts connected land cells. A visited matrix is used to ensure cells are only counted once. The main function iterates over all cells in the grid and updates the maximum area found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n), used for the visited matrix and recursion stack.

Try this approach in the editor →

Approach 2: Breadth First Search (BFS) Approach

A Breadth First Search (BFS) approach can also be used to solve this problem by iteratively exploring each cell's neighbors using a queue and counting the size of islands found. By enqueueing all land cell neighbors for exploration and tracking maximum sizes found, we can also determine the maximum island area.

This BFS C solution uses a queue to iteratively visit all land cells in a discovered island, marking them visited as they are dequeued. Queue-based exploration ensures that contiguous cells are considered in groups.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), since all cells are enqueued and dequeued once.
Space Complexity: O(m * n), required for the queue and the visited matrix.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth First Search (DFS) Approach

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n), used for the visited matrix and recursion stack.

Breadth First Search (BFS) Approach

Time Complexity: O(m * n), since all cells are enqueued and dequeued once.
Space Complexity: O(m * n), required for the queue and the visited matrix.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth First Search (DFS)O(m*n)O(m*n)Most common interview solution; simple recursive flood fill
Breadth First Search (BFS)O(m*n)O(m*n)When avoiding recursion depth or preferring iterative traversal
Union Find (Disjoint Set)O(m*n α(n))O(m*n)When modeling connected components or solving dynamic connectivity problems

Video Solution

Max Area of Island - Leetcode 695 - Python • NeetCode • 93,044 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Area of Island easy or hard?
Max Area of Island is classified as a Medium problem on LeetCode. The main challenge is recognizing it as a flood fill or graph traversal problem and correctly handling visited cells and grid boundaries.
Max Area of Island Python/Java solution
Python and Java implementations typically use DFS recursion or BFS with a queue. The algorithm scans the grid, triggers traversal when encountering land, and counts connected cells. Both languages achieve O(m*n) time complexity with straightforward grid iteration.
How to solve Max Area of Island in O(n)?
Treat the grid as a graph and perform DFS or BFS from every unvisited land cell. Expand in four directions and count the connected land cells belonging to that island. Because every cell is processed only once, the total complexity becomes O(m*n), which is linear in the number of cells.
What is the best approach for Max Area of Island?
Depth First Search (DFS) or Breadth First Search (BFS) flood fill is the best approach. Start from every unvisited land cell and expand to all connected neighbors while counting the island size. Both approaches visit each cell at most once, giving O(m*n) time complexity.
Is Max Area of Island asked at Google/Amazon/Meta?
Max Area of Island is a common grid traversal interview problem asked at companies like Amazon, Google, and Meta. It tests understanding of graph traversal, flood fill techniques, and matrix boundary handling.
What data structure is used in Max Area of Island?
The core data structures are a recursion stack for DFS or a queue for BFS. The grid itself acts as the graph, and many implementations modify the grid to mark visited cells instead of using a separate visited set.
What is the time complexity of Max Area of Island?
The optimal DFS or BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once during traversal. Space complexity is O(m*n) in the worst case due to recursion stack or the BFS queue.

Ready to solve this problem?

Practice Max Area of Island with our built-in code editor and test cases.

Practice on FleetCode
Previous

Battleships in a Board

Next

Detonate the Maximum Bombs