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 Sam K., 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

More Graphs practice problems

See all Graphs problems →