Scale Engineer

Min Cost to Connect All Points

Med
#1457Time: O(N^2 log N) - The number of edges `E` is O(N^2). Calculating all edge weights takes O(N^2). The dominant step is sorting these `E` edges, which takes O(E log E) = O(N^2 log(N^2)) = O(N^2 log N). The Union-Find operations for all edges take O(E * α(N)), where α is the very slow-growing inverse Ackermann function, making it nearly constant time per operation. This is overshadowed by the sorting time.Space: O(N^2) - We need to create and store a list of all possible edges between the N points. Since the graph is complete, there are O(N^2) edges. The Union-Find data structure requires an additional O(N) space.3 companies
Algorithms
Union FindMinimum Spanning Tree
Data structures
ArrayGraph
Companies
NutanixDE ShawDirecti

Prompt

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

 

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: 

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

 

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem as finding a Minimum Spanning Tree (MST) in a complete graph. The points are treated as vertices, and the weight of an edge between any two points is their Manhattan distance. Kruskal's algorithm is a classic method for finding an MST. It works by sorting all possible edges by weight and adding them to the MST one by one, as long as they don't form a cycle.

Algorithm

  • Create a list of all N*(N-1)/2 edges. Each edge connects a pair of points, and its weight is their Manhattan distance.
  • Sort this list of edges by weight in ascending order.
  • Initialize a Union-Find (also known as Disjoint Set Union or DSU) data structure with N components, one for each point.
  • Initialize total_cost = 0 and edge_count = 0.
  • Iterate through the sorted edges (u, v) with weight w:
    • If points u and v are not already in the same component (checked using the find operation):
      • Add the edge to the Minimum Spanning Tree (MST) by merging the components of u and v (using the union operation).
      • Add the edge's weight to the total_cost.
      • Increment edge_count.
    • Stop when edge_count reaches N-1, as the MST is complete.
  • Return total_cost.

Walkthrough

The core idea is to generate all possible connections (edges) between the points and then select the cheapest ones to form a tree that connects all points without cycles.

  1. Edge Generation: First, we compute the Manhattan distance between every pair of points. For N points, this results in N * (N - 1) / 2 edges. We store these edges, typically as a list of objects or tuples containing the two points and the distance.

  2. Sorting: We sort the list of all edges in non-decreasing order of their weights (distances).

  3. MST Construction: We use a Union-Find data structure to build the MST. This structure is initialized with each point in its own separate set. We then iterate through our sorted list of edges. For each edge, we check if its two endpoints are already in the same set. If they are not, adding the edge won't create a cycle. So, we add its weight to our total cost and merge the two sets using the union operation. We continue this process until we have added N - 1 edges, which is the number of edges in an MST for N vertices.

class Solution {    public int minCostConnectPoints(int[][] points) {        int n = points.length;        if (n <= 1) {            return 0;        }         List<Edge> edges = new ArrayList<>();        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);                edges.add(new Edge(i, j, dist));            }        }         Collections.sort(edges, (a, b) -> a.weight - b.weight);         UnionFind uf = new UnionFind(n);        int minCost = 0;        int edgesUsed = 0;         for (Edge edge : edges) {            if (uf.union(edge.u, edge.v)) {                minCost += edge.weight;                edgesUsed++;                if (edgesUsed == n - 1) {                    break;                }            }        }        return minCost;    }     class Edge {        int u, v, weight;        Edge(int u, int v, int weight) {            this.u = u;            this.v = v;            this.weight = weight;        }    }     class UnionFind {        int[] parent;        int[] rank;         UnionFind(int n) {            parent = new int[n];            rank = new int[n];            for (int i = 0; i < n; i++) {                parent[i] = i;            }        }         int find(int i) {            if (parent[i] == i) {                return i;            }            return parent[i] = find(parent[i]);        }         boolean union(int i, int j) {            int rootI = find(i);            int rootJ = find(j);            if (rootI != rootJ) {                if (rank[rootI] > rank[rootJ]) {                    parent[rootJ] = rootI;                } else if (rank[rootI] < rank[rootJ]) {                    parent[rootI] = rootJ;                } else {                    parent[rootJ] = rootI;                    rank[rootI]++;                }                return true;            }            return false;        }    }}

Complexity

Time

O(N^2 log N) - The number of edges `E` is O(N^2). Calculating all edge weights takes O(N^2). The dominant step is sorting these `E` edges, which takes O(E log E) = O(N^2 log(N^2)) = O(N^2 log N). The Union-Find operations for all edges take O(E * α(N)), where α is the very slow-growing inverse Ackermann function, making it nearly constant time per operation. This is overshadowed by the sorting time.

Space

O(N^2) - We need to create and store a list of all possible edges between the N points. Since the graph is complete, there are O(N^2) edges. The Union-Find data structure requires an additional O(N) space.

Trade-offs

Pros

  • It's a direct and conceptually clear application of a well-known MST algorithm.

  • The logic is relatively easy to follow if you are familiar with Kruskal's algorithm and Union-Find.

Cons

  • High space complexity due to the need to store all possible edges.

  • Slower than the optimized Prim's algorithm for dense graphs, which is the case in this problem.

Solutions

class Solution {public  int minCostConnectPoints(int[][] points) {    final int inf = 1 << 30;    int n = points.length;    int[][] g = new int[n][n];    for (int i = 0; i < n; ++i) {      int x1 = points[i][0], y1 = points[i][1];      for (int j = i + 1; j < n; ++j) {        int x2 = points[j][0], y2 = points[j][1];        int t = Math.abs(x1 - x2) + Math.abs(y1 - y2);        g[i][j] = t;        g[j][i] = t;      }    }    int[] dist = new int[n];    boolean[] vis = new boolean[n];    Arrays.fill(dist, inf);    dist[0] = 0;    int ans = 0;    for (int i = 0; i < n; ++i) {      int j = -1;      for (int k = 0; k < n; ++k) {        if (!vis[k] && (j == -1 || dist[k] < dist[j])) {          j = k;        }      }      vis[j] = true;      ans += dist[j];      for (int k = 0; k < n; ++k) {        if (!vis[k]) {          dist[k] = Math.min(dist[k], g[j][k]);        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem