Number of Islands
Problem Statement
You are given a map as a grid of characters. '1' is land and '0' is water. An island is a group of land cells joined up, down, left or right. Return how many islands there are. Two land cells that touch only at a corner are not joined.
grid, an m × n grid whose cells are the characters '0' or '1'.
The number of islands.
All the land cells are joined into one island.
The top-left 2×2 block is one island. The cell (2,2) touches that block only at a corner, so it is its own island. The cells (3,3) and (3,4) form the third island.
- • 1 ≤ m, n ≤ 300, where m is the number of rows and n is the number of columns
- • grid[i][j] is '0' or '1'
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Give each land cell its own name, let neighbours pass the smallest name, then count the names
Scan the grid; each land cell still unreached starts a new island: count it and sink the whole island
Give every land cell a unique name, its own index. Sweep the grid, and each land cell takes the smallest name among its land neighbours. Repeat sweeps until no name changes. Each island then shares one name, so the answer is the number of different names.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.