Log inSign up
mediumLeetCodeNot Started

Max Area of Island

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Grid with Multiple Islands:

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 maximum area island has 6 connected land cells.

Example 2 · All Water Grid:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Explanation: No islands exist in the grid.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Grid traversal and boundary condition validation
  • Depth-First Search (DFS) / Recursion on 2D grids
  • Breadth-First Search (BFS) with Queue

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate connected component area calculation recursively.
  • Master the in-place 'sinking island' pattern (grid[r][c] = 0) to track visited state.
  • Compare DFS call-stack memory vs BFS queue memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Number of IslandsSurrounded RegionsNumber of Closed Islands

1. Breadth-First Search from Every Land Cell (Brute Force)

Intuition

Iterate through each cell (r, c). When a cell with value 1 is found and not yet visited, enqueue it and run BFS in 4 directions, tracking visited cells. Update maxArea with the size of each component.

When to apply: Use to understand connected components in 4-directional grids.

BFS Island Exploration Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]
Current operationSTEP 1 OF 6
Grid: 4x4
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
0
↑ Scan
1
1
0
r1
0
1
0
0
r2
0
0
1
1
r3
0
0
1
1
Variables at this step
maxArea
0
Check / comparison
Start at (0,0)=0 (water).
Decision / next transition
Skip water cells.
Why this step matters

Grid: 4x4. Island 1 at top-left: (0,1), (0,2), (1,1). Island 2 at bottom-right: (2,2), (2,3), (3,2), (3,3).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int maxAreaOfIsland(int[][] grid) {
6 int m = grid.length, n = grid[0].length;
7 boolean[][] visited = new boolean[m][n];
8 int maxArea = 0;
9 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10
11 for (int r = 0; r < m; r++) {
12 for (int c = 0; c < n; c++) {
13 if (grid[r][c] == 1 && !visited[r][c]) {
14 Queue<int[]> q = new LinkedList<>();
15 q.add(new int[]{r, c});
16 visited[r][c] = true;
17 int area = 0;
18
19 while (!q.isEmpty()) {
20 int[] curr = q.poll();
21 area++;
22 for (int[] d : dirs) {
23 int nr = curr[0] + d[0], nc = curr[1] + d[1];
24 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && !visited[nr][nc]) {
25 visited[nr][nc] = true;
26 q.add(new int[]{nr, nc});
27 }
28 }
29 }
30 maxArea = Math.max(maxArea, area);
31 }
32 }
33 }
34 return maxArea;
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[][] grid = {
41 {0, 1, 1, 0},
42 {0, 1, 0, 0},
43 {0, 0, 1, 1},
44 {0, 0, 1, 1}
45 };
46 System.out.println("Max Area: " + sol.maxAreaOfIsland(grid));
47 }
48}

Time & Space Complexity

  • Time complexity: O(m * n) — Each cell is visited a constant number of times across BFS searches.
  • Space complexity: O(m * n) — Visited matrix and BFS queue store up to m*n elements.

Why Brute Force Doesn't Scale:

On large grids, allocating extra matrices strains garbage collection.

In-place sinking reuses the input matrix directly with 0 heap allocations.

2. Iterative Depth-First Search with Explicit Stack

Intuition

Push starting coordinates to an explicit stack. Pop and traverse neighbors, pushing unvisited land cells onto the stack and counting area until the stack is empty.

When to apply: Use in environments with restricted recursion call stack limits.

Iterative Stack DFS Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]
Current operationSTEP 1 OF 6
Stack pushes (0,1)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
0
1
↑ Stack Top
1
0
r1
0
1
0
0
r2
0
0
1
1
r3
0
0
1
1
Variables at this step
stack
["(0,1)"]
area
0
Check / comparison
Push to stack.
Decision / next transition
stack=[(0,1)], area=0.
Why this step matters

Stack pushes (0,1). Mark (0,1) visited.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int maxAreaOfIsland(int[][] grid) {
6 int m = grid.length, n = grid[0].length;
7 boolean[][] visited = new boolean[m][n];
8 int maxArea = 0;
9 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10
11 for (int r = 0; r < m; r++) {
12 for (int c = 0; c < n; c++) {
13 if (grid[r][c] == 1 && !visited[r][c]) {
14 Stack<int[]> stack = new Stack<>();
15 stack.push(new int[]{r, c});
16 visited[r][c] = true;
17 int area = 0;
18
19 while (!stack.isEmpty()) {
20 int[] curr = stack.pop();
21 area++;
22 for (int[] d : dirs) {
23 int nr = curr[0] + d[0], nc = curr[1] + d[1];
24 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && !visited[nr][nc]) {
25 visited[nr][nc] = true;
26 stack.push(new int[]{nr, nc});
27 }
28 }
29 }
30 maxArea = Math.max(maxArea, area);
31 }
32 }
33 }
34 return maxArea;
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[][] grid = {
41 {0, 1, 1, 0},
42 {0, 1, 0, 0},
43 {0, 0, 1, 1},
44 {0, 0, 1, 1}
45 };
46 System.out.println("Max Area: " + sol.maxAreaOfIsland(grid));
47 }
48}

Time & Space Complexity

  • Time complexity: O(m * n) — Every cell is pushed onto the stack at most once.
  • Space complexity: O(m * n) — Stack and visited matrix store up to m*n elements.

3. Recursive DFS with In-Place Grid Sinking (Optimal & Standard)

Intuition

1. For each cell: if grid[r][c] == 1, launch dfs(r, c). 2. Base case: If r or c out of bounds or grid[r][c] == 0, return 0. 3. Sink cell: grid[r][c] = 0. 4. Return 1 + sum of recursive DFS calls across 4 neighbors. Update maxArea with maximum returned area.

When to apply: Use as the clean StudyVex Gold Standard for grid connected component exploration.

Recursive DFS Grid Sinking Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]
Current operationSTEP 1 OF 6
grid[0][1]=1: Launch dfs(0, 1)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
0
0
↑ Sink (0,1)
1
0
r1
0
1
0
0
r2
0
0
1
1
r3
0
0
1
1
Variables at this step
sunken
["(0,1)"]
areaSoFar
1
Check / comparison
Sink (0,1).
Decision / next transition
grid[0][1] = 0, area = 1 + subproblems.
Why this step matters

grid[0][1]=1: Launch dfs(0, 1). Sink grid[0][1] = 0. Recurse right, down, left, up.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int maxAreaOfIsland(int[][] grid) {
6 int maxArea = 0;
7 for (int r = 0; r < grid.length; r++) {
8 for (int c = 0; c < grid[0].length; c++) {
9 if (grid[r][c] == 1) {
10 maxArea = Math.max(maxArea, dfs(grid, r, c));
11 }
12 }
13 }
14 return maxArea;
15 }
16
17 private int dfs(int[][] grid, int r, int c) {
18 if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
19 return 0;
20 }
21 grid[r][c] = 0; // sink
22 return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c) + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
23 }
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 int[][] grid = {
29 {0, 1, 1, 0},
30 {0, 1, 0, 0},
31 {0, 0, 1, 1},
32 {0, 0, 1, 1}
33 };
34 System.out.println("Max Area: " + sol.maxAreaOfIsland(grid));
35 }
36}

Time & Space Complexity

  • Time complexity: O(m * n) — Every cell is visited and flipped from 1 to 0 at most once.
  • Space complexity: O(m * n) — Recursive call stack takes O(m * n) worst case for snaking islands.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — BFS with Visited Set MatrixO(M * N)O(M * N)Maintain an explicit boolean visited[m][n] matrix. For every unvisited 1, launch a Queue BFS to count component size.Memory allocation for visited array.
2.Better — Iterative BFS with In-Place SinkingO(M * N)O(min(M, N))Whenever a 1 is seen, set grid[r][c] = 0 and push to queue. Expand 4 neighbors, sinking them upon enqueueing.Queue push/pop operations.
3.Optimal — Recursive DFS with In-Place SinkingOptimalO(M * N)O(M * N) call stackRecursive DFS returning 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1). Sink grid[r][c] = 0 immediately upon entry.None; optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All zero grid — Returns 0 since no land cells exist.
  • Single cell land grid [[1]] — Returns 1.
  • All 1s grid — Recursively visits every cell, returning M * N.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Ask the interviewer if mutating the input grid (grid[r][c] = 0) is acceptable or if a visited set is required.
  2. Clearly explain why the time complexity is strictly O(M * N) — each cell is visited at most 4 times by neighbor checks and sinks once.
  3. Mention BFS as an iterative alternative if stack depth is a concern.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Max Area of Island?

2.Why is the brute force approach suboptimal for large inputs in Max Area of Island?

3.Which data structure or technique enables the optimal solution for Max Area of Island?

Back to DSA Sheet