Nayan PahujaHey everyone! Welcome back to another day of problem-solving. It's day 49, and I'm still going strong on my quest for consistency. Today, We will be solving a problem using Disjoint Set Data Structure. So if you are unfamiliar with that, I would recommend you to please read DAY-46 this. It contains some context and necessary information to what it is and why we use it.
Question: Making a large Island
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
- Input: grid = [[1,0],[0,1]]
- Output: 3
- Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
- Input: grid = [[1,1],[1,0]]
- Output: 4
- Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Intuition:
- We have did some similar problems before including islands.
- What we did previously was we found out the number of islands using BFS/DFS approach.
- We can also say that an island is a connected component in graph.
- So by using Disjoint Set Data Structure we can find that an island which is connected to others 4 sided, will all come into one component.
- With the use case of DisjointSet we can find out the number of connected components and their sizes.
- Rest, we know that we can switch at most one Zero to 1. So we go through every 0 counting what would be total size of the island formed if we were to switch that zero to one and then we simply return the maximum island size we have found until now.
- This is kind of a solution where we are visiting every case.
- In case their is no 0 in the set we can simply return size of elements.
Algorithm:
1. Creating the Disjoint Set (DisjointSet Class):
- The code first sets up a Disjoint Set data structure, which allows us to group connected cells (land regions) together.
- It initializes the data structures for parent, rank, and size, necessary for the Disjoint Set.
- The unionBySize function performs the union operation on two sets, and findUPar function finds the representative (parent) of a set.
2. Traversing the Grid to Connect Land Regions:
- The code starts traversing the grid to find land cells (marked as 1).
- For each land cell, it checks its neighboring cells to see if they are also land cells (1).
- If neighboring cells are land cells, it merges the current land region with adjacent regions using the Disjoint Set's unionBySize function.
3. Finding the Largest Island:
- After merging all connected land regions, the code starts another grid traversal, but this time focusing on water cells (marked as 0).
- For each water cell, it checks its neighboring cells to find adjacent land regions.
- It keeps track of unique adjacent land regions using a set (components).
- For each adjacent land region, it calculates the total size by summing up their sizes in the Disjoint Set data structure.
- It adds 1 to the total size and compares it with the current maximum size (mx) to find the largest island considering the current water cell.
4. Finalizing the Result:
- After completing the grid traversal, the code checks each land region's size in the Disjoint Set data structure to find the maximum size of any single island.
- The code returns the maximum size (mx), representing the size of the largest island in the grid.
Code:
class DisjointSet {
public:
vector<int> rank, parent, size;
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;
}
}
int findUPar(int node) {
if (node == parent[node])
return node;
return parent[node] = findUPar(parent[node]);
}
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];
}
}
};
class Solution {
private:
bool isValid(int newr, int newc, int n) {
return newr >= 0 && newr < n && newc >= 0 && newc < n;
}
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
DisjointSet ds(n * n);
// step - 1
for (int row = 0; row < n ; row++) {
for (int col = 0; col < n ; col++) {
if (grid[row][col] == 0) continue;
int dr[] = { -1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};
for (int ind = 0; ind < 4; ind++) {
int newr = row + dr[ind];
int newc = col + dc[ind];
if (isValid(newr, newc, n) && grid[newr][newc] == 1) {
int nodeNo = row * n + col;
int adjNodeNo = newr * n + newc;
ds.unionBySize(nodeNo, adjNodeNo);
}
}
}
}
// step 2
int mx = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] == 1) continue;
int dr[] = { -1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};
set<int> components;
for (int ind = 0; ind < 4; ind++) {
int newr = row + dr[ind];
int newc = col + dc[ind];
if (isValid(newr, newc, n)) {
if (grid[newr][newc] == 1) {
components.insert(ds.findUPar(newr * n + newc));
}
}
}
int sizeTotal = 0;
for (auto it : components) {
sizeTotal += ds.size[it];
}
mx = max(mx, sizeTotal + 1);
}
}
for (int cellNo = 0; cellNo < n * n; cellNo++) {
mx = max(mx, ds.size[ds.findUPar(cellNo)]);
}
return mx;
}
};
Complexity Analysis:
Time: O(N^2logN)
Space: O(N^2)
Thanks for reading. Feedback is highly appreciated!
