FastPrep
Problem · Array

Number of Islands II

Learn this problem
● HardSpaceX logoSpaceXFULLTIMEPHONE SCREEN

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

drafts saved locally
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