Max Area of Island solution and explanation
Google
9 more videos on this problem
Max Area of Island - Leetcode 695 - PythonNeetCode · 11:14 · 93K views
Max Area of Island - Leetcode 695 - Graphs (Python)Greg Hogg · 11:15 · 12K views
Max Area of Island | LeetCode 695 | C++, PythonKnowledge Center · 20:20 · 4K views
Max Area of Island - LeetCode 695 PythonDeepti Talesra · 10:41 · 3K views
MAX AREA OF AN ISLAND | PYTHON | LEETCODE # 695Cracking FAANG · 12:03 · 2K views
Max Area of Island | Leetcode 695 | Live Coding sessionCoding Decoded · 9:33 · 2K views
Leetcode 695 - Max Area of Island (JAVA Solution Explained!)LC Bear · 13:18 · 644 views
Max Area of Island | LeetCode 695 DFS ExplainedDestination FAANG · 11:44 · 599 views
Leetcode 695. Max area of island - Solved Contact Tracing with Depth First SearchInterviewDose · 8:40 · 569 views
LEETCODE 695 MEDIUM - Max Area of Island - JAVASCRIPTIan Rosen · 12:14 · 328 views
The problem
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.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1.
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.
class Solution:
def dfs(self, grid, i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
return 0
grid[i][j] = 0 # Mark as visited
return 1 + self.dfs(grid, i + 1, j) + self.dfs(grid, i - 1, j) \
+ self.dfs(grid, i, j + 1) + self.dfs(grid, i, j - 1)
def maxAreaOfIsland(self, grid):
max_area = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
max_area = max(max_area, self.dfs(grid, i, j))
return max_areaclass Solution {
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0; // Mark as visited
return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j)
+ dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}
public int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
}
return maxArea;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
int dfs(std::vector<std::vector<int>>& grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0; // Mark as visited
return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j)
+ dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}
int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {
int max_area = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
max_area = std::max(max_area, dfs(grid, i, j));
}
}
}
return max_area;
}
};function dfs(grid, i, j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) {
return 0;
}
grid[i][j] = 0; // Mark as visited
return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j)
+ dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
}
var maxAreaOfIsland = function(grid) {
let maxArea = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
}
return maxArea;
};#include <stdio.h>
#define MAX 50
int dfs(int grid[MAX][MAX], int visited[MAX][MAX], int m, int n, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) {
return 0;
}
visited[i][j] = 1;
return 1 + dfs(grid, visited, m, n, i + 1, j)
+ dfs(grid, visited, m, n, i - 1, j)
+ dfs(grid, visited, m, n, i, j + 1)
+ dfs(grid, visited, m, n, i, j - 1);
}
int maxAreaOfIsland(int grid[MAX][MAX], int m, int n) {
int visited[MAX][MAX] = {0};
int max_area = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
int area = dfs(grid, visited, m, n, i, j);
if (area > max_area) {
max_area = area;
}
}
}
}
return max_area;
}
int main() {
int grid[MAX][MAX] = {{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}};
int m = 8, n = 13;
printf("Max area of island: %d", maxAreaOfIsland(grid, m, n));
return 0;
}public class Solution {
private int Dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0; // Mark as visited
return 1 + Dfs(grid, i + 1, j) + Dfs(grid, i - 1, j)
+ Dfs(grid, i, j + 1) + Dfs(grid, i, j - 1);
}
public int MaxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.Max(maxArea, Dfs(grid, i, j));
}
}
}
return maxArea;
}
}This Python solution achieves the same result by recursively exploring the grid using DFS. It updates the grid in place to mark visited cells and maintains a record of the largest island area encountered.
Time Complexity: O(m * n), since every cell in the grid is traversed.
Space Complexity: O(m * n), with recursion stack depth reaching max possible grid size.
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.
from collections import deque
class Solution:
def bfs(self, grid, i, j):
queue = deque([(i, j)])
area = 0
grid[i][j] = 0 # Mark as visited
while queue:
x, y = queue.popleft()
area += 1
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
newX, newY = x + dx, y + dy
if 0 <= newX < len(grid) and 0 <= newY < len(grid[0]) and grid[newX][newY] == 1:
grid[newX][newY] = 0 # Mark as visited
queue.append((newX, newY))
return area
def maxAreaOfIsland(self, grid):
max_area = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
max_area = max(max_area, self.bfs(grid, i, j))
return max_areaimport java.util.LinkedList;
import java.util.Queue;
class Solution {
private int bfs(int[][] grid, int i, int j) {
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = 0; // Mark as visited
int area = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
area++;
for (int[] dir : directions) {
int newX = current[0] + dir[0], newY = current[1] + dir[1];
if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 1) {
queue.offer(new int[]{newX, newY});
grid[newX][newY] = 0;
}
}
}
return area;
}
public int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, bfs(grid, i, j));
}
}
}
return maxArea;
}
}#include <vector>
#include <queue>
#include <algorithm>
class Solution {
public:
int bfs(std::vector<std::vector<int>>& grid, int i, int j) {
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::queue<std::pair<int, int>> q;
q.push({i, j});
grid[i][j] = 0; // Mark as visited
int area = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
area++;
for (auto& dir : directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < grid.size() && newY >= 0 && newY < grid[0].size() && grid[newX][newY] == 1) {
q.push({newX, newY});
grid[newX][newY] = 0;
}
}
}
return area;
}
int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {
int max_area = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
max_area = std::max(max_area, bfs(grid, i, j));
}
}
}
return max_area;
}
};function bfs(grid, i, j) {
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const queue = [[i, j]];
let area = 0;
grid[i][j] = 0;
while (queue.length > 0) {
const [x, y] = queue.shift();
area++;
for (const [dx, dy] of directions) {
const newX = x + dx, newY = y + dy;
if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] === 1) {
grid[newX][newY] = 0;
queue.push([newX, newY]);
}
}
}
return area;
}
var maxAreaOfIsland = function(grid) {
let maxArea = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
maxArea = Math.max(maxArea, bfs(grid, i, j));
}
}
}
return maxArea;
};#include <stdio.h>
#include <stdlib.h>
#define MAX 50
typedef struct {
int x, y;
} Point;
typedef struct {
Point* data;
int front, rear, size;
} Queue;
Queue* createQueue(int maxSize) {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->data = (Point*)malloc(maxSize * sizeof(Point));
queue->front = queue->rear = queue->size = 0;
return queue;
}
void enqueue(Queue* queue, Point item) {
queue->data[queue->rear++] = item;
queue->size++;
}
Point dequeue(Queue* queue) {
queue->size--;
return queue->data[queue->front++];
}
int bfs(int grid[MAX][MAX], int visited[MAX][MAX], int m, int n, int sx, int sy) {
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue* queue = createQueue(MAX * MAX);
enqueue(queue, (Point){sx, sy});
visited[sx][sy] = 1;
int area = 0;
while (queue->size) {
Point current = dequeue(queue);
area++;
for (int d = 0; d < 4; d++) {
int newX = current.x + directions[d][0];
int newY = current.y + directions[d][1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1 && !visited[newX][newY]) {
enqueue(queue, (Point){newX, newY});
visited[newX][newY] = 1;
}
}
}
free(queue->data);
free(queue);
return area;
}
int maxAreaOfIsland(int grid[MAX][MAX], int m, int n) {
int visited[MAX][MAX] = {0};
int max_area = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
int area = bfs(grid, visited, m, n, i, j);
if (area > max_area) {
max_area = area;
}
}
}
}
return max_area;
}
int main() {
int grid[MAX][MAX] = {{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}};
int m = 8, n = 13;
printf("Max area of island: %d", maxAreaOfIsland(grid, m, n));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private int Bfs(int[][] grid, int i, int j) {
int[][] directions = new int[][] {
new int[] {1, 0},
new int[] {-1, 0},
new int[] {0, 1},
new int[] {0, -1}
};
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((i, j));
grid[i][j] = 0;
int area = 0;
while (queue.Count > 0) {
var (x, y) = queue.Dequeue();
area++;
foreach (var dir in directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < grid.Length && newY >= 0 && newY < grid[0].Length && grid[newX][newY] == 1) {
queue.Enqueue((newX, newY));
grid[newX][newY] = 0;
}
}
}
return area;
}
public int MaxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.Max(maxArea, Bfs(grid, i, j));
}
}
}
return maxArea;
}
}This Python BFS solution uses a deque from the collections module to iteratively explore the grid in breadth-first manner, ensuring all discovered land is processed accurately.
Time Complexity: O(m * n), due to comprehensive traversal and cell parsing.
Space Complexity: O(min(m, n)), corresponding to the deque holding elements.
Approach 3: Default Approach
function maxAreaOfIsland(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number): number => {
if (grid[i][j] === 0) {
return 0;
}
let ans = 1;
grid[i][j] = 0;
for (let k = 0; k < 4; ++k) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (x >= 0 && x < m && y >= 0 && y < n) {
ans += dfs(x, y);
}
}
return ans;
};
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
}func maxAreaOfIsland(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if grid[i][j] == 0 {
return 0
}
ans := 1
grid[i][j] = 0
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n {
ans += dfs(x, y)
}
}
return ans
}
for i := range grid {
for j := range grid[i] {
ans = max(ans, dfs(i, j))
}
}
return
}impl Solution {
fn dfs(grid: &mut Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
if i == grid.len() || j == grid[0].len() || grid[i][j] == 0 {
return 0;
}
grid[i][j] = 0;
let mut res = 1 + Self::dfs(grid, i + 1, j) + Self::dfs(grid, i, j + 1);
if i != 0 {
res += Self::dfs(grid, i - 1, j);
}
if j != 0 {
res += Self::dfs(grid, i, j - 1);
}
res
}
pub fn max_area_of_island(mut grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut res = 0;
for i in 0..m {
for j in 0..n {
res = res.max(Self::dfs(&mut grid, i, j));
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(m * n), since every cell in the grid is traversed. |
| Breadth First Search (BFS) Approach | Time Complexity: O(m * n), due to comprehensive traversal and cell parsing. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When 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 |
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.