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.
m == grid.lengthn == grid[i].length1 ≤ m, n ≤ 300grid[i][j] is '0' or '1'.Perform a DFS or BFS traversal whenever you encounter a land node.
Read the grid like a map, row by row. The first time you step on a '1', you've found an island, so add one to the count. The hard part is the rest of that island. Later in the scan you'll step on more of its land, and none of it may be counted again.
Time O(mn)Space O(mn)
The full walkthrough and code in five languages, free to read
1