Number of Islands II
Number of Islands II is a hard graphs problem solved with the connected components pattern.
The best approach, optimal (union-find with a running count), runs in O(m · n + k · α(m · n)) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recount after each addition) up.
Problem
You have an m x n map that starts as pure water. You are given a list positions; the i-th entry [r, c] turns the cell in row r, column c into land.
An island is a group of land cells connected horizontally or vertically (diagonal contact does not count). After each operation, record how many islands exist on the map.
Return the list of counts, one per operation, in order.
Examples
Example 1
- Input
m = 3, n = 3, positions = [[0,0],[1,1],[0,1],[2,2],[1,2]]- Output
[1, 2, 1, 2, 1]- Why
- (1,1) starts a second island, (0,1) joins both, (2,2) is new, and (1,2) links it to the big island.
Example 2
- Input
m = 2, n = 3, positions = [[0,2],[1,0],[0,2],[1,1]]- Output
[1, 2, 2, 2]- Why
- The third operation repeats (0,2), so nothing changes; (1,1) touches (1,0) only, so it extends that island.
Example 3
- Input
m = 1, n = 1, positions = [[0,0]]- Output
[1]- Why
- The only cell becomes land, giving one island.
Constraints
1 <= m, n <= 10^4andm * n <= 10^41 <= positions.length <= 10^4positions[i] = [r, c]with0 <= r < mand0 <= c < n- The same cell may appear more than once in
positions.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recount after each addition) | O(k · m · n) | O(m · n) |
| Optimal (union-find with a running count) | O(m · n + k · α(m · n)) | O(m · n) |
1Brute force (recount after each addition)
O(k · m · n)k additions, and each one rescans the whole grid.O(m · n)The grid, a visited array and the BFS queue.Keep the grid. After turning each cell into land, run a full flood fill over the grid to count islands, and record that count.
- grid = m x n, all water.
- For each position: mark it as land.
- Count islands with BFS from every unvisited land cell; append the count.
class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
boolean[][] land = new boolean[m][n];
List<Integer> res = new ArrayList<>();
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int[] p : positions) {
land[p[0]][p[1]] = true;
boolean[][] seen = new boolean[m][n];
int count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (!land[i][j] || seen[i][j]) continue;
count++;
seen[i][j] = true;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] { i, j });
while (!q.isEmpty()) {
int[] c = q.poll();
for (int[] d : dirs) {
int r = c[0] + d[0], k = c[1] + d[1];
if (r >= 0 && k >= 0 && r < m && k < n && land[r][k] && !seen[r][k]) {
seen[r][k] = true;
q.add(new int[] { r, k });
}
}
}
}
res.add(count);
}
return res;
}
}class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
land = [[False] * n for _ in range(m)]
res = []
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for p in positions:
land[p[0]][p[1]] = True
seen = [[False] * n for _ in range(m)]
count = 0
for i in range(m):
for j in range(n):
if not land[i][j] or seen[i][j]:
continue
count += 1
seen[i][j] = True
q = deque([(i, j)])
while q:
cr, cc = q.popleft()
for dr, dc in dirs:
r, k = cr + dr, cc + dc
if 0 <= r < m and 0 <= k < n and land[r][k] and not seen[r][k]:
seen[r][k] = True
q.append((r, k))
res.append(count)
return resclass Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
vector<vector<bool>> land(m, vector<bool>(n, false));
vector<int> res;
int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (auto& p : positions) {
land[p[0]][p[1]] = true;
vector<vector<bool>> seen(m, vector<bool>(n, false));
int count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (!land[i][j] || seen[i][j]) continue;
count++;
seen[i][j] = true;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
auto c = q.front();
q.pop();
for (auto& d : dirs) {
int r = c.first + d[0], k = c.second + d[1];
if (r >= 0 && k >= 0 && r < m && k < n && land[r][k] && !seen[r][k]) {
seen[r][k] = true;
q.push({r, k});
}
}
}
}
res.push_back(count);
}
return res;
}
};function numIslands2(m, n, positions) {
const land = Array.from({ length: m }, () => new Array(n).fill(false));
const res = [];
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const p of positions) {
land[p[0]][p[1]] = true;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
let count = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) {
if (!land[i][j] || seen[i][j]) continue;
count++;
seen[i][j] = true;
const q = [[i, j]];
let head = 0;
while (head < q.length) {
const c = q[head++];
for (const d of dirs) {
const r = c[0] + d[0], k = c[1] + d[1];
if (r >= 0 && k >= 0 && r < m && k < n && land[r][k] && !seen[r][k]) {
seen[r][k] = true;
q.push([r, k]);
}
}
}
}
res.push(count);
}
return res;
}2Optimal (union-find with a running count)
O(m · n + k · α(m · n))Arrays are initialised once; each addition does at most 4 unions, each almost constant (α is the inverse Ackermann function).O(m · n)The parent and size arrays have one slot per cell.Give every cell an id r * n + c in a Disjoint Set Union. A new land cell adds one island. For each land neighbour, find both roots; if they differ, union them and subtract one island. A repeated cell changes nothing. Path compression and union by size make each operation almost O(1).
- parent[i] = -1 means water. On adding cell id: if already land, append count and continue.
- parent[id] = id, size[id] = 1, count++.
- For each of the 4 neighbours that is land: a = find(id), b = find(nb); if a != b, attach the smaller tree under the larger and count--.
- Append count.
class Solution {
private int[] parent, size;
public List<Integer> numIslands2(int m, int n, int[][] positions) {
parent = new int[m * n];
size = new int[m * n];
Arrays.fill(parent, -1);
List<Integer> res = new ArrayList<>();
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int count = 0;
for (int[] p : positions) {
int id = p[0] * n + p[1];
if (parent[id] != -1) { res.add(count); continue; }
parent[id] = id;
size[id] = 1;
count++;
for (int[] d : dirs) {
int r = p[0] + d[0], c = p[1] + d[1];
if (r < 0 || c < 0 || r >= m || c >= n) continue;
int nb = r * n + c;
if (parent[nb] == -1) continue;
int a = find(id), b = find(nb);
if (a == b) continue;
if (size[a] < size[b]) { int t = a; a = b; b = t; }
parent[b] = a;
size[a] += size[b];
count--;
}
res.add(count);
}
return res;
}
private int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
}class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
parent = [-1] * (m * n)
size = [0] * (m * n)
def find(x: int) -> int:
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root:
nxt = parent[x]
parent[x] = root
x = nxt
return root
res = []
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
count = 0
for pr, pc in positions:
idx = pr * n + pc
if parent[idx] != -1:
res.append(count)
continue
parent[idx] = idx
size[idx] = 1
count += 1
for dr, dc in dirs:
r, c = pr + dr, pc + dc
if r < 0 or c < 0 or r >= m or c >= n:
continue
nb = r * n + c
if parent[nb] == -1:
continue
a, b = find(idx), find(nb)
if a == b:
continue
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
count -= 1
res.append(count)
return resclass Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
parent.assign(m * n, -1);
sz.assign(m * n, 0);
vector<int> res;
int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int count = 0;
for (auto& p : positions) {
int id = p[0] * n + p[1];
if (parent[id] != -1) { res.push_back(count); continue; }
parent[id] = id;
sz[id] = 1;
count++;
for (auto& d : dirs) {
int r = p[0] + d[0], c = p[1] + d[1];
if (r < 0 || c < 0 || r >= m || c >= n) continue;
int nb = r * n + c;
if (parent[nb] == -1) continue;
int a = find(id), b = find(nb);
if (a == b) continue;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
count--;
}
res.push_back(count);
}
return res;
}
private:
vector<int> parent, sz;
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
};function numIslands2(m, n, positions) {
const parent = new Array(m * n).fill(-1);
const size = new Array(m * n).fill(0);
function find(x) {
let root = x;
while (parent[root] !== root) root = parent[root];
while (parent[x] !== root) {
const next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
const res = [];
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let count = 0;
for (const p of positions) {
const id = p[0] * n + p[1];
if (parent[id] !== -1) { res.push(count); continue; }
parent[id] = id;
size[id] = 1;
count++;
for (const d of dirs) {
const r = p[0] + d[0], c = p[1] + d[1];
if (r < 0 || c < 0 || r >= m || c >= n) continue;
const nb = r * n + c;
if (parent[nb] === -1) continue;
let a = find(id), b = find(nb);
if (a === b) continue;
if (size[a] < size[b]) { const t = a; a = b; b = t; }
parent[b] = a;
size[a] += size[b];
count--;
}
res.push(count);
}
return res;
}Edge cases to test
- A cell that is already land is added again (count stays the same)
- One new cell that merges up to four different islands at once
- Cells that touch only diagonally (still separate islands)
- A grid that is a single row or a single column
- Every cell of the grid eventually turned into land
Hints
Hint 1
After each addition you could recount islands from scratch, but that repeats almost all of the work every time.
Hint 2
A new land cell starts as its own island (+1). Each distinct neighbouring island it touches merges with it (-1 each).
Hint 3
A Disjoint Set Union (union-find) tells you in near O(1) whether two cells already belong to the same island, and merges them if not.
FAQ
What is the best time complexity for Number of Islands II?
Optimal (union-find with a running count) runs in O(m · n + k · α(m · n)) time and O(m · n) extra space. Arrays are initialised once; each addition does at most 4 unions, each almost constant (α is the inverse Ackermann function).
Which pattern does Number of Islands II use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.
Is there a brute force solution for Number of Islands II?
Yes. Brute force (recount after each addition) takes O(k · m · n) time and O(m · n) space. Keep the grid.
Which edge cases should I test for Number of Islands II?
A cell that is already land is added again (count stays the same); One new cell that merges up to four different islands at once; Cells that touch only diagonally (still separate islands); A grid that is a single row or a single column; Every cell of the grid eventually turned into land.