All problems

Number of Islands

Medium · graph traversal

You are given a map as a rectangular grid of characters. A cell holding "1" is land and a cell holding "0" is water.

An island is a group of land cells that are connected through shared edges: two land cells belong to the same island if you can walk from one to the other moving up, down, left or right over land only. Cells that touch only at a corner are not connected. Every cell outside the grid counts as water.

Return the number of islands in grid. You may change the grid while you work, only the number you return is checked.

Examples

Example 1

Input: grid = [["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]

Output: 1

Every land cell can be reached from every other one, so there is a single island.

Example 2

Input: grid = [["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]

Output: 3

The 2 x 2 block, the lone cell in row 2, and the pair in row 3 are three separate groups.

Example 3

Input: grid = [["1","0","0"], ["0","1","0"], ["0","0","1"]]

Output: 3

The three land cells only touch at corners, so each one is its own island.

Constraints