Problem Statement
In this problem, you are presented with a 2D grid simulation where initially, all cells are filled with water (represented by '0'). This grid has dimensions m by n. As part of the simulation, you are tasked with performing a series of operations where specific cells in the grid are transformed from water (0) to land (1). This task is guided by a series of positions, where each position specifies the row and column of the cell to be transformed.
Your goal is to determine the number of distinct islands present in the grid after each transformation operation. An "island" is defined as a cluster of adjacent lands (1's) connected either horizontally or vertically. It's also important to remember that the grid is surrounded entirely by water, isolating any potential land cells within from the edges.
Thus, for each position in the provided array positions, you will convert the specified cell to land and then have to count and return the number of connected groups of land cells (islands) after this transformation.
Examples
Example 1
Input:
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output:
[1,1,2,3]
Explanation:
Initially, the 2d grid is filled with water. - Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land. We have 1 island. - Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land. We still have 1 island. - Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land. We have 2 islands. - Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land. We have 3 islands.
Example 2
Input:
m = 1, n = 1, positions = [[0,0]]
Output:
[1]
Constraints
1 <= m, n, positions.length <= 1041 <= m * n <= 104positions[i].length == 20 <= ri < m0 <= ci < n
Approach and Intuition
To tackle this problem efficiently, we need an appropriate data structure that allows union-find operations. Both union and find are critical to efficiently determine whether adjacent cells are part of the same island or if they form a new island when a cell turns into land.
Initial Setup:
- Initialize the grid of size
m x nwith all values set to zero (water). - Prepare a union-find (disjoint set) structure to help manage and merge islands efficiently. Each cell has a unique identifier based on its row and column.
- Initialize the grid of size
Processing Operations:
- For each operation, convert the specified cell into land if it's not already land.
- For each newly converted land cell, check its four possible neighboring cells (up, down, left, right):
- If a neighboring cell is land, use the union operation to merge the sets, thus connecting components into a single island.
Counting Islands:
- After processing each operation, use the disjoint set structure to count the number of distinct sets (islands).
- Keep track of these counts and append to the result array.
Consider Edge Cases:
- Single cell grids where the output is straightforward with one transformation resulting in one island.
- Repetitive or consecutive operations on the same cell don't increase the number of islands.
- Large grids reaching the upper constraint limits should be handled efficiently without timeouts, validating the importance of the union-find structure’s nearly constant time operations.
By following this process, we can incrementally build up the grid's structure from water to land, efficiently merging islands and counting them as they form, which satisfies the problem requirements given by various operation constraints.
Solutions
- C++
- Java
class DisjointSet {
private:
vector<int> root, size;
int islands;
public:
DisjointSet(int capacity) {
root.resize(capacity, -1);
size.resize(capacity, 0);
islands = 0;
}
void plow(int i) {
if (root[i] != -1) return;
root[i] = i;
islands++;
}
bool checkPlowed(int i) {
return root[i] != -1;
}
int countIslands() { return islands; }
int locate(int i) {
if (root[i] != i) {
root[i] = locate(root[i]);
}
return root[i];
}
void link(int i, int j) {
int rootI = locate(i), rootJ = locate(j);
if (rootI == rootJ) {
return;
} else if (size[rootI] < size[rootJ]) {
root[rootI] = rootJ;
} else if (size[rootI] > size[rootJ]) {
root[rootJ] = rootI;
} else {
root[rootJ] = rootI;
size[rootI]++;
}
islands--;
}
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
vector<int> dirX = {-1, 1, 0, 0};
vector<int> dirY = {0, 0, -1, 1};
DisjointSet dsu(m * n);
vector<int> solution;
for (auto& pos : positions) {
int cell = pos[0] * n + pos[1];
dsu.plow(cell);
for (int d = 0; d < 4; d++) {
int adjX = pos[0] + dirX[d];
int adjY = pos[1] + dirY[d];
int neighborCell = adjX * n + adjY;
if (adjX >= 0 && adjX < m && adjY >= 0 && adjY < n && dsu.checkPlowed(neighborCell)) {
dsu.link(cell, neighborCell);
}
}
solution.push_back(dsu.countIslands());
}
return solution;
}
};
This C++ code snippet provides a solution for tracking the number of islands formed dynamically after successive land additions. Here's a quick breakdown of the classes and key methods used in the solution:
DisjointSet Class:
- This class is crucial for managing the connection and merging of land cells to form islands.
- Methods such as
plow,locate, andlinkhelp initialize land positions, find the root of each cell (with path compression), and union two land cells, respectively. - The method
countIslandsreturns the current count of disjoint sets or islands.
Solution Class:
- The main method
numIslands2inputs the grid dimensionsmandn, and a list of cell positions denoted as land. - Utilizing a
DisjointSetinstance, the function dynamically processes each land addition and uses adjacent direction vectors to check connectivity with neighboring cells that have been previously turned to land. - After processing each position, it appends the current island count to the result list which is then returned.
- The main method
Key steps include:
- Initializing the
DisjointSetwith a capacity equal to the total number of grid cells. - Iterating through each supplied position, marking it as land, and checking its 4 potential neighbors (up, down, left, right).
- If a neighbor is land, it is unioned using the
linkmethod. - Recording the number of distinct islands after adding each new land cell.
The approach effectively maintains a running count of separate islands using union-find (disjoint set) data structure, optimizing the union and find operations to efficiently handle potentially large inputs.
class DisjointSets {
int[] root;
int[] size;
int count;
public DisjointSets(int maxElements) {
root = new int[maxElements];
size = new int[maxElements];
for (int i = 0; i < maxElements; i++)
root[i] = -1;
count = 0;
}
public void makeSet(int x) {
if (root[x] >= 0)
return;
root[x] = x;
count++;
}
public boolean hasLand(int x) {
return root[x] >= 0;
}
int getTotalIslands() {
return count;
}
public int findParent(int x) {
if (root[x] != x)
root[x] = findParent(root[x]);
return root[x];
}
public void merge(int x, int y) {
int rootX = findParent(x), rootY = findParent(y);
if (rootX == rootY) {
return;
} else if (size[rootX] < size[rootY]) {
root[rootX] = rootY;
} else if (size[rootX] > size[rootY]) {
root[rootY] = rootX;
} else {
root[rootY] = rootX;
size[rootX]++;
}
count--;
}
}
class IslandCalculator {
public List<Integer> calculateIslands(int m, int n, int[][] positions) {
int dirsX[] = { -1, 1, 0, 0 };
int dirsY[] = { 0, 0, -1, 1 };
DisjointSets disjointSet = new DisjointSets(m * n);
List<Integer> result = new ArrayList<>();
for (int[] pos : positions) {
int currentLand = pos[0] * n + pos[1];
disjointSet.makeSet(currentLand);
for (int i = 0; i < 4; i++) {
int adjX = pos[0] + dirsX[i];
int adjY = pos[1] + dirsY[i];
int adjPosition = adjX * n + adjY;
if (adjX >= 0 && adjX < m && adjY >= 0 && adjY < n && disjointSet.hasLand(adjPosition)) {
disjointSet.merge(currentLand, adjPosition);
}
}
result.add(disjointSet.getTotalIslands());
}
return result;
}
}
Looking at the given Java code, you'll find two main classes: DisjointSets and IslandCalculator. The code is designed to solve the dynamic connectivity problem related to finding the number of islands in a grid, as new land positions are added over time.
First, grasp the role of each class:
DisjointSets:- It manages the union-find data structure with path compression and union by rank. It helps in efficiently connecting components (islands) and finding the root of any element.
makeSetinitializes a position as new land if it's water initially.hasLandchecks if a position already has land.findParentfinds the root of an element, compressing the path as it recurses.mergeconnects two lands if they are not already connected, thereby potentially reducing the count of distinct islands.getTotalIslandsreturns the current count of distinct islands.
IslandCalculator:- It computes the number of islands after each land addition in the grid.
- It uses a
DisjointSetsinstance to manage the state of the grid. - Iterates over the given positions, placing land and merging with adjacent positions if they are also land.
When working with this code to calculate the number of islands after each operation:
- Initialize a
DisjointSetfor all possible positions in the grid (m * n). - Iterate over each position from the input list, making it a new land.
- For each new land position, check all four possible adjacent positions (up, down, left, right).
- If an adjacent is within bounds and is already land, merge it with the current position.
- After processing each new position, append the current number of distinct islands to the result list.
Through this approach, you dynamically calculate connected components or islands in a grid with each land addition. This solution is efficient for scenarios where connectivity changes over time and you need to keep track of components (or islands) count dynamically.
No comments yet.