How should I practice Count Islands After Land Additions?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Count Islands After Land Additions associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Count Islands After Land Additions

Learn this problem

● Hard

GoogleFULLTIMEONSITE INTERVIEW

See Google hiring insights

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, return the number of islands. 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

countIslandsAfterAdditions(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.