FastPrep
Problem · Array

Number of Islands II

Learn this problem
● HardAmazon logoAmazonONSITE INTERVIEW
See Amazon hiring insights

Problem statement

Start with an m by n grid containing only water. For each distinct position [row, col] in positions, turn that cell into land and append the current number of islands to the result.

An island is a maximal group of land cells connected vertically or horizontally. Diagonal cells are not connected.

Interview follow-up

The rest of the discussion covered the DSU approach, how union-find works, edge cases, and the time and space complexity.

Function

numIslands2(m: int, n: int, positions: int[][]) → int[]

Examples

Example 1

m = 3n = 3positions = [[0,0],[0,1],[1,2],[2,1]]return = [1,1,2,3]

The second cell joins the first island. The final two additions are not four-directionally adjacent to existing land.

Example 2

m = 2n = 2positions = [[0,0],[1,1],[0,1]]return = [1,2,1]

The third addition connects the two existing islands into one.

More Amazon problems

drafts saved locally
public int[] numIslands2(int m, int n, int[][] positions) {
  // write your code here
}
m3
n3
positions[[0,0],[0,1],[1,2],[2,1]]
expected[1,1,2,3]
checking account