FastPrepNumber of Islands with Diagonal Connectivity

Number of Islands with Diagonal Connectivity

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given a non-empty rectangular binary matrix grid, return the number of islands.

An island is a maximal group of cells containing 1. Two land cells belong to the same island when they touch horizontally, vertically, or diagonally. In other words, each cell has up to eight neighbors.

Cells containing 0 are water. You may modify grid.

Function

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

Examples

Example 1

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

All three land cells connect through diagonals, so they form one island.

Example 2

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

The upper-left land group and the rightmost vertical pair do not touch in any of the eight directions.

Example 3

grid = [[0,0],[0,0]]return = 0

The matrix contains no land cells.

Constraints

  • 1 <= grid.length <= 500.
  • 1 <= grid[i].length <= 500.
  • Every row has the same length.
  • grid[i][j] is either 0 or 1.
  • You may modify grid.

More Google problems

See Google hiring insights
public int countIslands(int[][] grid) {
  // write your code here
}
grid[[1,0,0],[0,1,0],[0,0,1]]
expected1
Checking account…