Skip to main content

695. Max Area of Island

medium

Given a binary grid, return the area of the largest island (a 4-connected region of 1s). Same DFS scaffolding as Number of Islands, but the recursion returns a count instead of just marking.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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 largest island has area 6.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

This is Number of Islands with a twist — instead of counting islands, you want the max size of any one.

Hint 2

Run DFS from every unvisited 1. The DFS returns the count of cells it flooded. Take the max across all DFS launches.

Hint 3

Flip 1s to 0s as you visit so each cell contributes to exactly one DFS call.

Solution approach

Reveal approach

Iterate the grid. For each cell that's a 1, launch a DFS that returns the area of the connected component containing it. The DFS: if out of bounds or current cell is 0 return 0; otherwise mark current as 0 (so we don't revisit) and return 1 + sum of recursive calls on the 4 neighbors. Track the max return value across all outer-loop launches. The flip-in-place trick avoids a separate visited set and guarantees each cell is processed exactly once across all DFS calls combined. BFS works identically — same complexity, queue instead of stack. O(m*n) time, O(m*n) recursion depth worst-case.

Complexity

Time
O(m*n)
Space
O(m*n)

Related patterns

  • graph-dfs
  • graph-bfs
  • matrix
  • flood-fill

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Max Area of Island and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →