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 1s.

Example 1:

COPY

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:

COPY

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:

COPY

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++).