827. Making A Large Island

Problem Statement

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.

Example 3:

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

Constraints:

• n == grid.length

• n == grid[i].length

• 1 <= n <= 500

• grid[i][j] is either 0 or 1.

Intuition

Approach:

Treat already cluster of 1s as a whole component,
Make Disjoint set of that

Now for every zero, Try to find adjacent compoenets and add to check if 
answer increases

One thing to node *** Size[i] denotes number of nodes in that component in DS

Also, store ultimate parent of all neoghbours in set, while traversing for zeros
To avoid multiple values of same compoenets


Atlast, Traverse again for no zero case, to get final anwer

Links

https://leetcode.com/problems/making-a-large-island/description/

Video Links

https://www.youtube.com/watch?v=lgiz0Oup6gM&ab_channel=takeUforward

Approach 1:

TC = N^2

C++

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 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]++; 
        }
    }

    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 {
public:
    bool check_val(int x, int y, int n){
        return x>=0 and y>=0 and x<n and y<n;
    }

    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        DisjointSet ds(n*n);
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        for(int row=0; row<n; row++){
            for(int col=0; col<n; col++){
                if(grid[row][col] == 0) continue;

                for(int i=0; i<4; i++){
                    int nrow = row + dx[i];
                    int ncol = col + dy[i];

                    if(check_val(nrow, ncol, n) and grid[nrow][ncol] == 1){
                        int node = row*n+col;
                        int adj_node = nrow*n + ncol;
                        ds.unionBySize(node, adj_node);
                    }
                }
            }
        }

        int maxi = 0;

        for(int row=0; row<n; row++){
            for(int col=0; col<n; col++){
                if(grid[row][col] == 1) continue;

                set<int> components;
                for(int i=0; i<4; i++){
                    int nrow = row + dx[i];
                    int ncol = col + dy[i];

                    if(check_val(nrow, ncol, n) and grid[nrow][ncol] == 1){
                        int node = nrow * n+ ncol;
                        components.insert(ds.findUPar(node));
                    }
                }
                int temp_sum=0;
                for(auto &it: components){
                    temp_sum += ds.size[it];
                }

                maxi = max(maxi, temp_sum + 1);
            }
        }

        for(int i=0; i<n*n; i++){
            maxi = max(maxi, ds.size[ds.findUPar(i)]);
        }

        return maxi;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems