Photo by bady abbas on Unsplash

# Solving LC Hard — Making A Large Island using a Disjoint Set

## This Coding Chronicles post discusses a step-by-step solution for the Leetcode Hard problem '827. Making A Large Island'.

# Problem Description

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 `1`

s.

**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.
```

**Example 3:**

```
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
```

# Intuition

First, we will find the largest island in the matrix. This will be our answer if we do 0 operations.

Now we can perform one operation, where we can convert any "0" cells to "1".

Some possible cases:

We increase an already existing island by converting a neighboring "0" to "1", increasing its component size by 1.

We can connect two islands that have one "0" cell separating them. We can convert that "0" to "1", which causes both islands to form one big island. Answer in that case

`= size(island1) + size(island2) + 1`

.

# Approach

Let’s use a disjoint set to store the islands in our matrix. We will iterate over all cells with value "1", and iterate on the neighboring cells. If we find a neighbor with value = "1", we will perform a union between the vertices, because they will be part of the same island.

We will store a `largestComponentSize`

attribute in our disjoint set which keeps track of the largest component size, so we don’t have to worry about finding the largest island of the matrix. We try to update `largestComponentSize`

whenever we perform a union between two vertices.

After storing the existing islands of the matrix, we will iterate over all "0" cells and find the largest island we can form by converting that cell to "1".

We will iterate over the neighbors and sum the island sizes.

# Code

```
class DisjointSet{
public:
vector<int> parent, size;
int largestComponentSize = 0;
DisjointSet(int n){
parent.resize(n+1);
size.resize(n+1,1);
for(int i=0; i<=n; i++)
parent[i] = i;
largestComponentSize = 1;
}
int find(int a){
if(parent[a] != a){
parent[a] = find(parent[a]);
}
return parent[a];
}
void unify(int a, int b){
a = find(a);
b = find(b);
if(a == b)
return;
if(size[a] < size[b])
swap(a,b);
parent[b] = a;
size[a] += size[b];
largestComponentSize = max(largestComponentSize, size[a]);
}
};
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
class Solution {
public:
int largestIsland(vector<vector<int>>& a) {
int n = a.size();
DisjointSet ds(n*n);
int ans = 0;
// Storing islands in ds
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(a[i][j] == 1){
int u = i*n + j;
// Neighbouring vertices
for(int k=0; k<4; k++){
int ni = i+dx[k], nj = j+dy[k];
if(ni<0 || nj<0 || ni>n-1 || nj>n-1 || a[ni][nj] == 0)
continue;
int v = ni*n+nj;
ds.unify(u,v);
}
}
ans = max(ans, ds.largestComponentSize);
}
}
cout<<ans<<endl;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(a[i][j] == 1)
continue;
int res = 1;
set<int> st;
for(int k=0; k<4; k++){
int ni = i+dx[k], nj = j+dy[k];
if(ni<0 || nj<0 || ni>n-1 || nj>n-1 || a[ni][nj] == 0)
continue;
int v = ni*n+nj;
st.insert(ds.find(v));
}
for(auto s : st){
res += ds.size[s];
}
ans = max(ans, res);
}
}
return ans;
}
};
```

# Time Complexity and Space Complexity of the Solution

**Time complexity:** O(4N^2+4N^2) = O(N^2) since we are only iterating over the neighbors for every cell (Beats 97.87% of users with C++).

**Space complexity:** O(N^2) for disjoint set vectors (Beats 82.25% of users with C++).