FastPrep
Problem · Matrix

Count Islands with DFS and BFS

Learn this problem
● MediumVisa logoVisaNEW GRADOA

Problem statement

You are given a rectangular binary grid in which 1 is land and 0 is water. An island is a maximal group of land cells connected horizontally or vertically.

Return the number of islands. Depth-first search and breadth-first search are alternative required solution strategies for the same result; the function returns one count.

Function

countIslands(grid: int[][]) → int

Examples

Example 1

grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]return = 2

The upper-left land cells form one island, and the connected right-side cells form the other.

Example 2

grid = [[1,0,1],[0,1,0],[1,0,1]]return = 5

Diagonal contact does not connect land, so every 1 is a separate island.

Example 3

grid = []return = 0

An empty grid contains no land.

Constraints

  • 0 <= rows, columns <= 500.
  • The grid is rectangular and contains at most 200000 cells.
  • Every cell is either 0 or 1.

More Visa problems

drafts saved locally
public int countIslands(int[][] grid) {
  // write your code here
}
grid[[1,1,0,0],[1,0,0,1],[0,0,1,1]]
expected2
checking account