200. Number of Islands

How to solve Number of Islands (LeetCode 200): the approach in brief

The 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.

Pattern

Number of Islands is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph DFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Approach outline

1. Consider modeling the grid as a graph where each cell is a node, and land cells ('1') are potential connected components.
2. Think about how you can traverse the grid to identify connected components — what graph traversal algorithms can help explore all connected land cells?
3. When you find a land cell that hasn't been visited, use DFS or BFS to explore all adjacent land cells (up, down, left, right) and mark them as visited to avoid counting them multiple times.

Complexity

The reference solution runs in O(m * n) time and O(m * n) space.

Asked at

Number of Islands has been reported in interviews at Amazon, Bloomberg, Microsoft, Oracle, Facebook, Apple, Uber, Google.