LEARNING JOURNAL

function minCostConnectPoints(points: number[][]): number {
  const edges:Edge[] = [];

  for(let i = 0; i < points.length -1; i++) {
      for(let j = i + 1; j < points.length; j++){
          edges.push(new Edge(points[i], i, points[j], j));
      }
  }

  edges.sort((e1, e2) => e1.getDist() - e2.getDist()); 
  let cost = 0;

  const uF = new UnionFind(points.length);

  for(let i = 0; i < edges.length; i++) {
      const e = edges[i];

      const v1 = e.either();
      const v2 = e.other(v1);

      if(!uF.isSameGroup(v1, v2)){
          const groupSize = uF.union(v1,v2);
          cost += e.getDist();  
          
          if(groupSize === points.length)
            break;
      } 
  }

  return cost;
};


class Edge {
    private p1:number;
    private p2:number;
    private distance: number;

    constructor(p1: number[], iP1:number, p2: number[], iP2:number){
        this.p1 = iP1;
        this.p2 = iP2;
        this.distance = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }
    
    getDist():number{
        return this.distance;
    }

    either():number{
        return this.p1;
    }

    other(v:number):number{
        if(v === this.p1) return this.p2;

        return this.p1;
    }
    
}

class UnionFind {
    private roots:number[];
    private groupSizes:number[];

    constructor(length:number){
        this.roots = Array(length).fill(0).map((_,i) => i);
        this.groupSizes = Array(length).fill(1);
    }
    
    isSameGroup(v1:number, v2:number):boolean {
        const root1 = this.findRoot(v1);
        const root2 = this.findRoot(v2);

        return root1 === root2;
    }


    union(v1:number, v2:number):number {
        const root1 = this.findRoot(v1);
        const root2 = this.findRoot(v2);

        if(this.groupSizes[root1] < this.groupSizes[root2]){
                       
            this.roots[root1] = root2;
            this.groupSizes[root2] += this.groupSizes[root1];

            return this.groupSizes[root2];
        }
        else {
            this.roots[root2] = root1;
            this.groupSizes[root1] += this.groupSizes[root2];

            return this.groupSizes[root1];
        }

        
    }

    private findRoot(v:number) {
        if(this.roots[v] === v)
            return v;

        this.roots[v] = this.findRoot(this.roots[v]);

        return this.roots[v];
    }
}