135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180
class DisjointSet {
    // Constructor
    constructor(n) {
        /* To store the ranks, parents and 
        sizes of different set of vertices */
        this.rank = new Array(n + 1).fill(0);
        this.parent = new Array(n + 1).fill(0).map((_, i) => i);
        this.size = new Array(n + 1).fill(1);
    }

    // Function to find ultimate parent
    findUPar(node) {
        if (node === this.parent[node])
            return node;
        this.parent[node] = this.findUPar(this.parent[node]);
        return this.parent[node];
    }

    // Function to implement union by rank
    unionByRank(u, v) {
        const ulp_u = this.findUPar(u);
        const ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v) return;
        if (this.rank[ulp_u] < this.rank[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
        } else if (this.rank[ulp_v] < this.rank[ulp_u]) {
            this.parent[ulp_v] = ulp_u;
        } else {
            this.parent[ulp_v] = ulp_u;
            this.rank[ulp_u]++;
        }
    }

    // Function to implement union by size
    unionBySize(u, v) {
        const ulp_u = this.findUPar(u);
        const ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v) return;
        if (this.size[ulp_u] < this.size[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
            this.size[ulp_v] += this.size[ulp_u];
        } else {
            this.parent[ulp_v] = ulp_u;
            this.size[ulp_u] += this.size[ulp_v];
        }
    }

    getSize(node) {
        return this.size[this.findUPar(node)];
    }
}

// Solution class
class Solution {
    // DelRow and delCol for neighbors
    constructor() {
        this.delRow = [-1, 0, 1, 0];
        this.delCol = [0, 1, 0, -1];
    }

    // Helper function to check if a pixel is within boundaries
    isValid(i, j, n) {
        // Return false if pixel is invalid
        if (i < 0 || i >= n) return false;
        if (j < 0 || j >= n) return false;
        // Return true if pixel is valid
        return true;
    }

    /* Function to add initial islands to 
    the disjoint set data structure */
    addInitialIslands(grid, ds, n) {
        // Traverse all the cells in the grid
        for (let row = 0; row < n; row++) {
            for (let col = 0; col < n; col++) {
                // If the cell is not land, skip
                if (grid[row][col] === 0) continue;

                // Traverse on all the neighbors
                for (let ind = 0; ind < 4; ind++) {
                    // Get the coordinates of neighbor
                    const newRow = row + this.delRow[ind];
                    const newCol = col + this.delCol[ind];

                    // If the cell is valid and a land cell
                    if (this.isValid(newRow, newCol, n) && grid[newRow][newCol] === 1) {
                        // Get the number for node
                        const nodeNo = row * n + col;
                        // Get the number for neighbor
                        const adjNodeNo = newRow * n + newCol;

                        /* Take union of both nodes as 
                        they are part of the same island */
                        ds.unionBySize(nodeNo, adjNodeNo);
                    }
                }