Graph BFS / DFS
LC #200Medium
Number of Islands
Graph BFS / DFS
AmazonGoogleMetaBloombergMicrosoftProblem
Count the number of islands (connected groups of '1') in a 2D grid.
graphdfsbfsmatrixunion-find
Constraints
- ›1 ≤ m, n ≤ 300
- ›grid[i][j] is '0' (water) or '1' (land)
- ›Connected = 4-directional (up, down, left, right)
Example
Input
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]Output
3Why
Three connected groups of '1'. Diagonal connections do NOT count