Skip to main content

200. Number of Islands

medium

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. The canonical grid-as-graph problem — DFS/BFS flood fill with in-place marking is the muscle memory every interviewer probes for.

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

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Constraints

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

Examples

Example 1

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

Example 2

Input
grid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]
Output
3

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

Iterate every cell. When you find a '1', you found a new island — but you need a way to not double-count its connected neighbors.

Hint 2

Use DFS or BFS from that cell, marking every connected '1' as visited (or flipping it to '0' in place) so you only count each island once.

Hint 3

Increment counter on each fresh '1' you encounter at the outer loop level; recurse/queue into all 4-directional neighbors that are also '1', marking them as you go.

Solution approach

Reveal approach

Iterate the grid with a double loop. When you hit a '1', increment the island counter and launch a DFS (or BFS) from that cell. The DFS marks the current cell as visited (flipping it to '0' in place is the slickest version — no extra visited set), then recurses into the 4 cardinal neighbors that are in-bounds and still '1'. After the DFS returns, the entire connected component has been flattened to '0' so the outer loop won't re-trigger on any of its cells. Continue scanning. Return the counter when the loops finish. O(m*n) time since every cell is visited a constant number of times; O(m*n) space worst-case for the recursion stack on a fully-land grid (use BFS with a queue if that's a concern).

Complexity

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

Related patterns

  • dfs
  • bfs
  • union-find
  • 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 Number of Islands and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →