Problem Statement
Given n, m denoting the row and column of the 2D matrix, and an array A of size k denoting the number of operations. Matrix elements are 0 if there is water or 1 if there is land. Originally, the 2D matrix is all 0 which means there is no land in the matrix. The array has k operator(s) and each operator has two integers A[i][0], A[i][1] means that you can change the cell matrix[A[i][0]][A[i][1]] from sea to island. Return how many islands are there in the matrix after each operation.
The answer array will be of size k.
Examples
Example 1:
Input: n = 4, m = 5, k = 4,
A = [
[1,1],
[0,1],
[3,3],
[3,4]
]
Output: [1, 1, 2, 2]
Explanation: The following illustration is the representation of the operation:
Example 2:
Input: n = 4, m = 5, k = 12,
A = [
[0,0],
[0,0],
[1,1],
[1,0],
[0,1],
[0,3],
[1,3],
[0,4],
[3,2],
[2,2],
[1,2],
[0,2]
]
Output: [1, 1, 2, 1, 1, 2, 2, 2, 3, 3, 1, 1]
Different Approaches
1️⃣ Disjoint Set Data Structure
Intuition:
It is clear that there is a need to find the number of islands after every operation. This implies that the problem statement refers to a dynamic graph (where edges are added after every operation). In such cases, the Disjoint Set data structure plays a huge role, using which the union(merge) operation can be performed in constant time.
Understanding:
Each cell in the matrix can be represented as a node in the disjoint set. An edge will be identified to be present between two land cells if and only if both the cells are in the same column or same row.
Every time a new cell is converted from sea to land, it can be assumed to be a single island, incrementing the count of islands by one. For every neighboring islands, the merging can be performed and the count of islands can be decremented with each merge.
How to store cells as nodes in the Disjoint Set?
The cells can be numbered sequentially as shown in the following figure:
Thus, a number can be assigned to a cell having coordinates (i, j) in the following way:
Node number = (i*n) + j, where n is the number of columns in the grid.
Approach:
- Initialize a Disjoint Set Union (DSU) to manage the union and find operations for connected components. Use a visited matrix to keep track of cells that have been converted to land.
- For each operation, convert the specified water cell to land:
- If the cell is already land, skip to the next operation.
- Assume the new land cell starts as a new island.Examine the four possible neighboring cells (up, down, left, right):
- If a neighboring cell is also land, attempt to union the current cell with the neighboring cell.
- If the cells are not already connected, decrement the island count and union the sets.
- After processing each operation, store the current number of islands.
- Output the number of islands after each operation.
Code:
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
public:
/* To store the ranks, parents and
sizes of different set of vertices */
vector<int> rank, parent, size;
// Constructor
DisjointSet(int n) {
rank.resize(n + 1, 0);
parent.resize(n + 1);
size.resize(n + 1);
for (int i = 0; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
}
// Function to find ultimate parent
int findUPar(int node) {
if (node == parent[node])
return node;
return parent[node] = findUPar(parent[node]);
}
// Function to implement union by rank
void unionByRank(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (rank[ulp_u] < rank[ulp_v]) {
parent[ulp_u] = ulp_v;
}
else if (rank[ulp_v] < rank[ulp_u]) {
parent[ulp_v] = ulp_u;
}
else {
parent[ulp_v] = ulp_u;
rank[ulp_u]++;
}
}
// Function to implement union by size
void unionBySize(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (size[ulp_u] < size[ulp_v]) {
parent[ulp_u] = ulp_v;
size[ulp_v] += size[ulp_u];
}
else {
parent[ulp_v] = ulp_u;
size[ulp_u] += size[ulp_v];
}
}
};
// Solution class
class Solution{
private:
// DelRow and delCol for neighbors
vector<int> delRow = {-1, 0, 1, 0};
vector<int> delCol = {0, 1, 0, -1};
/* Helper Function to check if a
pixel is within boundaries */
bool isValid(int &i, int &j,
int &n, int &m) {
// Return false if pixel is invalid
if(i < 0 || i >= n) return false;
if(j < 0 || j >= m) return false;
// Return true if pixel is valid
return true;
}
public:
/* Function to return the nunmber
of islands after each operation */
vector<int> numOfIslands(int n, int m,
vector<vector<int>> &A) {
// Disjoint set Data structure
DisjointSet ds(n * m);
// Visited array
int vis[n][m];
memset(vis, 0, sizeof vis);
// To store the count of islands
int cnt = 0;
// To store the result
vector<int> ans;
// Perform each operation
for (auto it : A) {
int row = it[0]; // Row
int col = it[1]; // Column
/* If already a land cell, no new
islands will be formed */
if (vis[row][col] == 1) {
ans.push_back(cnt);
continue;
}
// Make the cell as land
vis[row][col] = 1;
/* Increment the count considering
the land cell was alone */
cnt++;
// Check all the neighbors
for (int ind = 0; ind < 4; ind++) {
// Get the coordinates of cell
int newRow = row + delRow[ind];
int newCol = col + delCol[ind];
// If the cell is a valid land cell
if (isValid(newRow, newCol, n, m) &&
vis[newRow][newCol] == 1) {
// Get the node and adjacent node number
int nodeNo = row * m + col;
int adjNodeNo = newRow * m + newCol;
// If not already conencted, perfom the union
if (ds.findUPar(nodeNo) !=
ds.findUPar(adjNodeNo)) {
// Decrement count
cnt--;
// Perform the union
ds.unionBySize(nodeNo, adjNodeNo);
}
}
}
/* Store the number of islands after
current operation in the result list */
ans.push_back(cnt);
}
// Return the result
return ans;
}
};
int main() {
int n = 4, m = 5, k = 4;
vector<vector<int>> A = {
{1,1},
{0,1},
{3,3},
{3,4}
};
// Creating instance of Solution class
Solution sol;
/* Function call to return the number
of islands after each operation */
vector<int> ans = sol.numOfIslands(n, m, A);
// Output
cout << "The number of islands after each operations are: ";
for(int i=0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}Complexity Analysis:
- Time Complexity:
O(K*4ɑ)- Each operation involves converting the sea cell to land cell and merging the nodes (if possible) taking an overall O(4ɑ) time. Since, there are a total of K operations, the overall time complexity is O(K*4ɑ).
- Space Complexity:
O(K) + O(N*M)- The result list takes O(K) space. The visited array takes O(N*M) space and the Disjoint set uses parent and rank/size array storing all N*M nodes taking O(N*M) space.