Number of Islands

medium

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 surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Test Cases

Copy an input into the main harness and Run to verify

Input

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

Expected Output

1

Input

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

Expected Output

3

Constraints

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

Hints

Hint 1 — click to reveal

Every time you find unvisited land, that is a new island.

Hint 2 — click to reveal

DFS/BFS from it to mark the whole island visited.

Java Compiler