Min Cost to Connect All Points LeetCode solution in Java

1
class Solution {
2
  public int minCostConnectPoints(int[][] points) {
3
    int len = points.length;
4
    // array that keep track of the shortest distance from mst to each node
5
    int[] disArr = new int[len];
6
    for (int i = 1; i < len; ++i) {
7
      disArr[i] = Integer.MAX_VALUE;
8
    }
9
    // visited[node] == true if node in mst
10
    boolean[] visited = new boolean[len];
11
    visited[0] = true;
12

13
    int numEdge = 0;
14
    // current node, used to update the disArr
15
    int cur = 0;
16
    // result
17
    int res = 0;
18

19
    while (numEdge++ < len - 1) {
20
      int minEdge = Integer.MAX_VALUE;
21
      int next = -1;
22
      for (int i = 0; i < len; ++i) {
23
        // if the node i is not in mst
24
        if (!visited[i]) {
25
          // find the distance between cur and i
26
          int dis =
27
              Math.abs(points[cur][0] - points[i][0]) + Math.abs(points[cur][1] - points[i][1]);
28
          // update distance array
29
          disArr[i] = Math.min(dis, disArr[i]);
30
          // find the shortest edge
31
          if (disArr[i] < minEdge) {
32
            minEdge = disArr[i];
33
            next = i;
34
          }
35
        }
36
      }
37
      cur = next;
38
      visited[cur] = true;
39
      res += minEdge;
40
    }
41

42
    return res;
43
  }
44
}