DSA problem

Number of Islands

MediumDepth First Search (DFS)Pattern: Depth First Search (DFS)top75FreeAmazonMicrosoftGoogleMetaApple

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 a maximal group of '1' cells connected 4-directionally (horizontally or vertically), and you may assume all four edges of the grid are surrounded by water.

The problem reduces to counting connected components in an implicit graph where vertices are land cells and edges connect orthogonally adjacent land cells. Each connected component corresponds to one island. To count components we can sweep the grid; whenever we find an unvisited land cell, we launch a full traversal that marks every land cell reachable from it, then increment the count.

DFS and BFS both work; DFS is the slightly simpler implementation because Python/JS/C++ recursion is concise. We mutate the grid in place to record visited cells — flipping each visited '1' to '0' — which removes the need for a separate visited matrix. This is acceptable because the problem allows destroying the input grid, and it keeps space usage to just the recursion stack.

The optimal implementation is therefore: iterate every cell. If it is land, increment count and DFS-sink the whole island by flipping all reachable '1's to '0'. The grid is touched a constant number of times per cell, giving O(m * n) time. Recursion depth is bounded by the largest island, so worst-case space is O(m * n) on a fully-land grid.

Examples

Constraints

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

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

dfsmatrixgraphconnected-components

Browse all DSA problems