Number of Islands

Given a grid of '1' (land) and '0' (water), count the islands. An island is land connected horizontally or vertically.

A way to picture it

You're a pilot mapping an archipelago. Fly over row by row. Whenever you spot land nobody has claimed, plant a flag, then send a flood of explorers across every connected patch so that island can never be counted again.

How to approach it

Scan every cell. On unvisited land, add one to the count and flood-fill (DFS/BFS) the whole island, marking it visited.

Example

Input: {"grid":[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]}. Output: 1.

Complexity: O(m · n) time and O(m · n) space. Each cell is flooded at most once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.