305. Number of Islands II
Number of Islands II (LeetCode 305) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
How to solve Number of Islands II
Number of Islands II is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.
Work towards the solution in these steps:
- Consider representing the grid as a graph where land cells are nodes and edges connect adjacent lands; think about how islands relate to connected components in this graph.
- After each land addition, you need to efficiently update and count the number of connected components; which data structure can help dynamically manage and merge these components?
- Union-Find (Disjoint Set Union) is ideal here for merging adjacent lands; how can you map the 2D grid positions to a 1D structure suitable for Union-Find operations?
The reference solution runs in O(k * α(k)) time and O(m * n) space.
The Number of Islands II solution and editorial walks through the full approach with reference code.
Problem statement
You are given two integers m and n representing the number of rows and columns of a 2D grid, initially filled with water (0). You are also given a list of positions positions, where each positions[i] = [ri, ci] represents adding a land cell (1) at position (ri, ci) in the grid.
An island is a group of connected land cells (horizontally or vertically adjacent). After each addition of land, you must determine the current number of islands in the grid.
Return a list of integers representing the number of islands after each operation in positions.
Constraints: - 1 <= m, n <= 10^4 - 0 <= positions.length <= min(m n, 10^4) - positions[i].length == 2 - 0 <= ri < m, 0 <= ci < n - No position is repeated in positions
You should return a list of length positions.length, where the i-th element is the number of islands after adding land at positions[i].
Examples
Example 1
Input: {"m": 3, "n": 3, "positions": [[0, 0], [0, 1], [1, 2], [2, 1]]}
Output: [1, 1, 2, 3]
Explanation: Each addLand operation creates a new island except for the second operation, which connects to the first land.
Example 2
Input: {"m": 3, "n": 3, "positions": [[0, 0], [0, 1], [1, 2], [1, 1]]}
Output: [1, 1, 2, 1]
Explanation: The last operation connects two islands into one, reducing the count.
Topics and companies
Topics: Array, Hash Table, Union Find.
Reported in interviews at Amazon.
How to practise Number of Islands II on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(k * α(k)) time and O(m * n) space.
Open Number of Islands II in the code editor, or read the Number of Islands II editorial for a worked solution with its approach and complexity analysis.
Where Number of Islands II sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Union-Find (Disjoint Set Union - DSU) subpattern
- The full DSA patterns sheet
Problems related to Number of Islands II
Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:
- Accounts Merge — Medium, same subpattern
- Graph Valid Tree — Medium, same subpattern
- Greatest Common Divisor Traversal — Hard, same subpattern
- Largest Component Size by Common Factor — Hard, same subpattern
- Most Stones Removed with Same Row or Column — Medium, same subpattern
- Number of Connected Components in an Undirected Graph — Medium, same subpattern
Number of Islands II FAQ
What is the LeetCode number of Number of Islands II?
Number of Islands II is LeetCode problem 305, rated Hard.
What pattern is used to solve Number of Islands II?
Number of Islands II is a Union-Find problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
What is the time complexity of Number of Islands II?
The reference solution runs in O(k * α(k)) time and O(m * n) space.
Which companies ask Number of Islands II?
Number of Islands II has been reported in interviews at Amazon.