1584. Min Cost to Connect All Points LeetCode Solution

In this guide, you will get 1584. Min Cost to Connect All Points LeetCode Solution with the best time and space complexity. The solution to Min Cost to Connect All Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Min Cost to Connect All Points solution in C++
4. Min Cost to Connect All Points solution in Java
5. Min Cost to Connect All Points solution in Python
6. Additional Resources

Problem Statement of Min Cost to Connect All Points

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.

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(1)

1584. Min Cost to Connect All Points LeetCode Solution in C++

class Solution {
 public:
  int minCostConnectPoints(vector<vector<int>>& points) {
    // dist[i] := the minimum distance to connect the points[i]
    vector<int> dist(points.size(), INT_MAX);
    int ans = 0;

    for (int i = 0; i < points.size() - 1; ++i) {
      for (int j = i + 1; j < points.size(); ++j) {
        // Try to connect the points[i] with the points[j].
        dist[j] = min(dist[j], abs(points[i][0] - points[j][0]) +
                                   abs(points[i][1] - points[j][1]));
        // Swap the points[j] (the point with the mnimum distance) with the
        // points[i + 1].
        if (dist[j] < dist[i + 1]) {
          swap(points[j], points[i + 1]);
          swap(dist[j], dist[i + 1]);
        }
      }
      ans += dist[i + 1];
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1584. Min Cost to Connect All Points LeetCode Solution in Java

class Solution {
  public int minCostConnectPoints(int[][] points) {
    // dist[i] := the minimum distance to connect the points[i]
    int[] dist = new int[points.length];
    Arrays.fill(dist, Integer.MAX_VALUE);
    int ans = 0;

    for (int i = 0; i < points.length - 1; ++i) {
      for (int j = i + 1; j < points.length; ++j) {
        // Try to connect the points[i] with the points[j].
        dist[j] = Math.min(dist[j], Math.abs(points[i][0] - points[j][0]) +
                                        Math.abs(points[i][1] - points[j][1]));
        // Swap the points[j] (the point with the minimum distance) with the
        // points[i + 1].
        if (dist[j] < dist[i + 1]) {
          final int[] tempPoint = points[j];
          points[j] = points[i + 1];
          points[i + 1] = tempPoint;
          final int tempDist = dist[j];
          dist[j] = dist[i + 1];
          dist[i + 1] = tempDist;
        }
      }
      ans += dist[i + 1];
    }

    return ans;
  }
}
// code provided by PROGIEZ

1584. Min Cost to Connect All Points LeetCode Solution in Python

class Solution:
  def minCostConnectPoints(self, points: list[int]) -> int:
    # dist[i] := the minimum distance to connect the points[i]
    dist = [math.inf] * len(points)
    ans = 0

    for i in range(len(points) - 1):
      for j in range(i + 1, len(points)):
        # Try to connect the points[i] with the points[j].
        dist[j] = min(dist[j], abs(points[i][0] - points[j][0]) +
                      abs(points[i][1] - points[j][1]))
        # Swap the points[j] (the point with the mnimum distance) with the
        # points[i + 1].
        if dist[j] < dist[i + 1]:
          points[j], points[i + 1] = points[i + 1], points[j]
          dist[j], dist[i + 1] = dist[i + 1], dist[j]
      ans += dist[i + 1]

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.