Number of Islands

Medium · Graphs

You are given a 2D grid made of the characters "1" (land) and "0" (water), representing a map. An island is a group of land cells connected horizontally or vertically (not diagonally), surrounded by water or the edge of the grid. Count how many separate islands exist in the grid.

Examples

Input:  grid = [["1","1","0","0"],["1","1","0","0"],["0","0","1","0"],["0","0","0","1"]]
Output: 3
Why:    The top-left 2x2 block of land is one connected island, the single '1' in the third row is a second island, and the '1' in the bottom-right corner is a third island.

Input:  grid = [["0","0","0"],["0","0","0"]]
Output: 0
Why:    There is no land cell anywhere, so there are no islands.

Input:  grid = [["1","1","1"],["1","1","1"]]
Output: 1
Why:    All land cells are connected into a single block, forming one island.

Constraints

1 <= grid.length, grid[0].length <= 300, grid[i][j] is either "0" or "1"

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Number of Islands

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Number of Islands. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.