LeetCode 1584 - Min Cost to Connect All Points

This problem asks us to connect all given points on a 2D plane with the minimum possible total cost. Each point is repre

leetcodemediumarrayunion-findgraph-theoryminimum-spanning-tree

LeetCode Problem 1584

Difficulty: 🟡 Medium
Topics: Array, Union-Find, Graph Theory, Minimum Spanning Tree

Solution

Problem Understanding

This problem asks us to connect all given points on a 2D plane with the minimum possible total cost. Each point is represented as a pair of coordinates [x, y]. The cost of connecting two points is defined as their Manhattan distance:

$$|x_i - x_j| + |y_i - y_j|$$

The goal is to ensure that every point becomes connected, either directly or indirectly, while minimizing the total connection cost.

The statement also says that there must be exactly one simple path between every pair of points. This condition describes a tree structure. In graph theory, a connected graph with no cycles and n - 1 edges is called a spanning tree. Since we want the minimum total edge cost, this becomes a classic Minimum Spanning Tree problem.

We can think of the problem as building a complete weighted graph:

  • Every point is a node
  • Every pair of points has an edge
  • The edge weight is the Manhattan distance between those points

Then we must find the Minimum Spanning Tree of this graph.

The constraints are important:

  • Up to 1000 points
  • Coordinates can be large, both positive and negative
  • All points are distinct

A complete graph with 1000 points contains:

$$\frac{1000 \times 999}{2} = 499500$$

possible edges. This is large, but still manageable for efficient MST algorithms such as Prim's or Kruskal's algorithm.

Several edge cases are important:

  • A single point requires no connections, so the answer is 0
  • Points may have negative coordinates, so absolute differences must be handled carefully
  • Multiple edges can have the same weight
  • A naive recursive graph traversal could become inefficient if cycles are not managed correctly
  • Generating all edges explicitly may consume significant memory if not handled carefully

Approaches

Brute Force Approach

The brute force idea is to generate every possible way to connect points and then choose the valid connected structure with minimum total cost.

For n points, there are exponentially many subsets of edges. We would need to check whether each subset forms a valid spanning tree and then compute its total weight. This quickly becomes computationally impossible.

Another less extreme brute force method is:

  1. Generate all pairwise edges
  2. Sort them
  3. Try combinations of edges until finding the minimum valid spanning tree

Even this becomes infeasible because the number of edge combinations grows explosively.

Although brute force guarantees correctness by exhaustively exploring possibilities, it cannot handle 1000 points within reasonable time limits.

Optimal Approach

The key observation is that this is exactly a Minimum Spanning Tree problem.

A Minimum Spanning Tree connects all nodes:

  • Using exactly n - 1 edges
  • Without cycles
  • With minimum total edge weight

Two classic algorithms solve MST problems efficiently:

  • Kruskal's Algorithm
  • Prim's Algorithm

For this problem, Prim's Algorithm is especially attractive because we do not need to explicitly store all edges. Since the graph is complete, storing all pairwise edges would require nearly 500,000 edges.

Instead, Prim's Algorithm incrementally grows the tree:

  • Start from one point
  • Repeatedly connect the nearest unvisited point
  • Keep track of the minimum known connection cost for each point

This avoids explicitly constructing the full graph while still achieving the correct minimum cost.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all possible connection combinations
Optimal, Prim's Algorithm O(n²) O(n) Efficient MST construction without storing all edges

Algorithm Walkthrough

We use Prim's Algorithm to build the Minimum Spanning Tree.

Step 1: Initialize tracking structures

We maintain three main pieces of information:

  • visited[i], whether point i has already been added to the MST
  • min_distance[i], the cheapest known cost to connect point i
  • total_cost, the running MST cost

Initially:

  • Start from point 0
  • Set its connection cost to 0
  • Set every other point's cost to infinity

This means point 0 is chosen as the starting node.

Step 2: Repeatedly select the cheapest unvisited point

At every iteration:

  1. Find the unvisited point with the smallest connection cost
  2. Add it to the MST
  3. Add its cost to total_cost

This greedy step is the core of Prim's Algorithm.

The selected point is guaranteed to be the cheapest valid expansion of the current tree.

Step 3: Update neighboring connection costs

After adding a new point to the MST:

  1. Compute its Manhattan distance to every unvisited point
  2. If this new distance is smaller than the currently known minimum cost, update it

This step continuously maintains the cheapest possible connection into the growing tree.

Step 4: Continue until all points are connected

We repeat the process exactly n times.

After all points are visited:

  • Every point belongs to the MST
  • Exactly n - 1 connections were effectively chosen
  • The total cost is minimized

Why it works

Prim's Algorithm works because of the cut property of Minimum Spanning Trees.

At every step, the algorithm chooses the minimum weight edge connecting the current tree to an unvisited node. This greedy choice is always safe because any MST must contain the cheapest edge crossing such a cut.

By repeatedly applying this rule, the algorithm constructs a globally optimal Minimum Spanning Tree.

Python Solution

from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)

        if n == 1:
            return 0

        visited = [False] * n
        min_distance = [float("inf")] * n

        min_distance[0] = 0
        total_cost = 0

        for _ in range(n):
            current = -1

            for i in range(n):
                if not visited[i]:
                    if current == -1 or min_distance[i] < min_distance[current]:
                        current = i

            visited[current] = True
            total_cost += min_distance[current]

            x1, y1 = points[current]

            for neighbor in range(n):
                if not visited[neighbor]:
                    x2, y2 = points[neighbor]

                    distance = abs(x1 - x2) + abs(y1 - y2)

                    if distance < min_distance[neighbor]:
                        min_distance[neighbor] = distance

        return total_cost

The implementation directly follows Prim's Algorithm.

The visited array tracks which points are already part of the MST. This prevents cycles and ensures each point is added exactly once.

The min_distance array stores the minimum known connection cost for every point. Initially, all values are infinity except the starting point, which has cost 0.

Inside the outer loop, we search for the unvisited point with the smallest connection cost. This point becomes the next MST node.

After selecting the point, we compute Manhattan distances from it to every remaining unvisited point. If a newly discovered connection is cheaper than the previously known cost, we update min_distance.

At the end of the process, total_cost contains the weight of the Minimum Spanning Tree.

Go Solution

package main

import "math"

func minCostConnectPoints(points [][]int) int {
	n := len(points)

	if n == 1 {
		return 0
	}

	visited := make([]bool, n)
	minDistance := make([]int, n)

	for i := 0; i < n; i++ {
		minDistance[i] = math.MaxInt32
	}

	minDistance[0] = 0
	totalCost := 0

	for i := 0; i < n; i++ {
		current := -1

		for j := 0; j < n; j++ {
			if !visited[j] {
				if current == -1 || minDistance[j] < minDistance[current] {
					current = j
				}
			}
		}

		visited[current] = true
		totalCost += minDistance[current]

		x1, y1 := points[current][0], points[current][1]

		for neighbor := 0; neighbor < n; neighbor++ {
			if !visited[neighbor] {
				x2, y2 := points[neighbor][0], points[neighbor][1]

				distance := abs(x1-x2) + abs(y1-y2)

				if distance < minDistance[neighbor] {
					minDistance[neighbor] = distance
				}
			}
		}
	}

	return totalCost
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation mirrors the Python solution closely.

Go does not provide a built in absolute value function for integers, so we define a helper abs function.

Slices are used instead of Python lists. The math.MaxInt32 constant initializes distances to a very large value.

Since Go integers are large enough for the given constraints, integer overflow is not an issue here.

Worked Examples

Example 1

Input:

points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Initial State

Point Min Distance Visited
0 0 False
1 inf False
2 inf False
3 inf False
4 inf False

Total cost = 0

Iteration 1

Choose point 0.

Distances from point 0:

To Distance
1 4
2 13
3 7
4 7

Updated state:

Point Min Distance Visited
0 0 True
1 4 False
2 13 False
3 7 False
4 7 False

Total cost = 0

Iteration 2

Choose point 1 with cost 4.

Distances from point 1:

To Distance
2 9
3 3
4 7

Updated state:

Point Min Distance Visited
0 0 True
1 4 True
2 9 False
3 3 False
4 7 False

Total cost = 4

Iteration 3

Choose point 3 with cost 3.

Distances from point 3:

To Distance
2 10
4 4

Updated state:

Point Min Distance Visited
0 0 True
1 4 True
2 9 False
3 3 True
4 4 False

Total cost = 7

Iteration 4

Choose point 4 with cost 4.

Distance update:

To Distance
2 14

No improvement for point 2.

Total cost = 11

Iteration 5

Choose point 2 with cost 9.

Final total cost:

20

Example 2

Input:

points = [[3,12],[-2,5],[-4,1]]

Initial State

Point Min Distance Visited
0 0 False
1 inf False
2 inf False

Iteration 1

Choose point 0.

Distances:

To Distance
1 12
2 18

Iteration 2

Choose point 1.

Distances:

To Distance
2 6

Update point 2 from 18 to 6.

Iteration 3

Choose point 2.

Total cost:

0 + 12 + 6 = 18

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Each iteration scans all points and updates all distances
Space O(n) Arrays for visited state and minimum distances

The algorithm runs n iterations. In each iteration:

  • We scan all points to find the next minimum node
  • We scan all points again to update distances

This gives:

$$O(n \times n) = O(n^2)$$

The space usage is linear because we only maintain a few arrays of size n.

Test Cases

from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)

        if n == 1:
            return 0

        visited = [False] * n
        min_distance = [float("inf")] * n

        min_distance[0] = 0
        total_cost = 0

        for _ in range(n):
            current = -1

            for i in range(n):
                if not visited[i]:
                    if current == -1 or min_distance[i] < min_distance[current]:
                        current = i

            visited[current] = True
            total_cost += min_distance[current]

            x1, y1 = points[current]

            for neighbor in range(n):
                if not visited[neighbor]:
                    x2, y2 = points[neighbor]

                    distance = abs(x1 - x2) + abs(y1 - y2)

                    if distance < min_distance[neighbor]:
                        min_distance[neighbor] = distance

        return total_cost

solution = Solution()

assert solution.minCostConnectPoints(
    [[0,0],[2,2],[3,10],[5,2],[7,0]]
) == 20  # provided example 1

assert solution.minCostConnectPoints(
    [[3,12],[-2,5],[-4,1]]
) == 18  # provided example 2

assert solution.minCostConnectPoints(
    [[0,0]]
) == 0  # single point

assert solution.minCostConnectPoints(
    [[0,0],[1,1]]
) == 2  # simple two-point connection

assert solution.minCostConnectPoints(
    [[-1,-1],[1,1]]
) == 4  # negative coordinates

assert solution.minCostConnectPoints(
    [[0,0],[2,0],[4,0],[6,0]]
) == 6  # points on straight line

assert solution.minCostConnectPoints(
    [[0,0],[0,0],[1,1]]
) == 2  # duplicate coordinates scenario if allowed

assert solution.minCostConnectPoints(
    [[1000000,1000000],[-1000000,-1000000]]
) == 4000000  # large coordinate values
Test Why
[[0,0],[2,2],[3,10],[5,2],[7,0]] Validates standard MST construction
[[3,12],[-2,5],[-4,1]] Tests negative coordinates
[[0,0]] Single node edge case
[[0,0],[1,1]] Smallest nontrivial graph
[[-1,-1],[1,1]] Confirms absolute value handling
[[0,0],[2,0],[4,0],[6,0]] Linear structure
[[0,0],[0,0],[1,1]] Tests duplicate coordinates handling
[[1000000,1000000],[-1000000,-1000000]] Large coordinate stress test

Edge Cases

Single Point

If the input contains only one point, no edges are required because the graph is already connected.

This case can easily cause issues if the algorithm assumes at least one edge exists. The implementation handles this by immediately returning 0 when n == 1.

Negative Coordinates

Coordinates may be negative, so Manhattan distance calculations must use absolute values correctly.

An incorrect implementation might accidentally subtract coordinates directly without applying abs, producing invalid negative distances. Both solutions explicitly compute:

$$|x_1 - x_2| + |y_1 - y_2|$$

which guarantees correctness regardless of coordinate signs.

Large Coordinate Values

Coordinates may be as large as 10^6.

This means Manhattan distances can become quite large. An implementation using small integer types could overflow. Python integers automatically expand as needed, and Go's standard int type safely handles these values on LeetCode platforms.

Dense Complete Graph

Every point can connect to every other point, producing nearly 500,000 edges for the maximum input size.

A naive adjacency list storing all edges would consume unnecessary memory. The chosen Prim's Algorithm implementation computes distances on demand instead of storing the entire graph, keeping space complexity linear.