FastPrepNumber of Islands II

Number of Islands II

SpaceX logoSpaceX● HardFULLTIMEPHONE SCREEN
Learn

Problem statement

Start with a rows by cols grid containing only water. Process each position in positions in order by turning that cell into land.

After every addition, append the current number of islands to the result. An island is a maximal group of land cells connected vertically or horizontally. Adding a cell that is already land changes nothing but still produces an output.

Function

numIslands2(rows: int, cols: int, positions: int[][]) → int[]

Examples

Example 1

rows = 3cols = 3positions = [[0,0],[0,1],[1,2],[2,1],[1,1]]return = [1,1,2,3,1]

The final center cell joins the three existing components into one island.

Example 2

rows = 1cols = 3positions = [[0,1],[0,1],[0,0],[0,2]]return = [1,1,1,1]

The repeated addition is a no-op, and both later cells attach to the existing island.

Example 3

rows = 2cols = 2positions = [[0,0],[1,1],[0,1],[1,0]]return = [1,2,1,1]

Diagonal cells are separate. Adding either remaining edge-adjacent cell merges them.

Constraints

  • 1 <= rows, cols <= 1000.
  • 1 <= positions.length <= 100000.
  • Every position is [row, col] with 0 <= row < rows and 0 <= col < cols.
  • Positions may repeat.

More SpaceX problems

See SpaceX hiring insights
public int[] numIslands2(int rows, int cols, int[][] positions) {
    // Write your code here.
}
rows3
cols3
positions[[0,0],[0,1],[1,2],[2,1],[1,1]]
expected[1,1,2,3,1]
Checking account…