Minimum Cost to Connect Points

TIP103 Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Graphs, Minimum Spanning Tree (MST), Prim's Algorithm, Heaps

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does it mean for all points to be connected with exactly one path between any two of them?

  • A: The connections must form a spanning tree: every point is reachable from every other point, and with N points we use exactly N - 1 edges, so there are no cycles.

• Q: How is the cost of connecting two points calculated?

  • A: The cost is the Manhattan distance between them: |x1 - x2| + |y1 - y2|.

• Q: Can we connect any pair of points, or only certain pairs?

  • A: Any pair of points can be connected directly, so conceptually we are working with a complete graph where every pair of points has an edge weighted by its Manhattan distance.

HAPPY CASE
Input: points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
Output: 20
Explanation: Connect (0,0)-(2,2) for cost 4, (2,2)-(5,2) for cost 3, (5,2)-(7,0) for cost 4, and (2,2)-(3,10) for cost 9. Total = 4 + 3 + 4 + 9 = 20, and every point can reach every other point by exactly one path.

Input: points = [[3, 12], [-2, 5], [-4, 1]]
Output: 18
Explanation: Connect (3,12)-(-2,5) for cost 12 and (-2,5)-(-4,1) for cost 6. Total = 12 + 6 = 18.

EDGE CASE
Input: points = [[2, 3]]
Output: 0
Explanation: A single point needs no connections, so the total cost is 0.

Input: points = [[1, 1], [1, 1]]
Output: 0
Explanation: Two points at the same coordinates have a Manhattan distance of 0, so connecting them costs nothing.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Connecting All Nodes at Minimum Total Cost, we can consider the following approaches:

• Minimum Spanning Tree (MST): Connecting all points with exactly one path between any two of them, at minimum total edge weight, is the definition of an MST on the complete graph of points.
• Prim's Algorithm: Grow the tree one point at a time, always adding the cheapest edge from the tree to an unvisited point, using a min-heap to pick that edge efficiently.
• Kruskal's Algorithm with Union-Find: Sort all pairwise edges by cost and add each edge that joins two different components. This also works, but generating and sorting all O(N^2) edges makes Prim's a more natural fit for a dense, complete graph.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Treat the points as nodes of a complete graph where each edge weight is the Manhattan distance between two points. Run Prim's algorithm: start from any point, and repeatedly use a min-heap to pull out the cheapest edge that reaches a point not yet in the tree. Each time we absorb a new point, push the edges from it to all remaining unvisited points. After all N points have been absorbed, the accumulated cost is the minimum total cost.

1) If there is at most one point, return 0.
2) Initialize a `visited` list, a running `total_cost` of 0, a counter of connected points, and a min-heap seeded with (0, 0) — cost 0 to bring point 0 into the tree.
3) While fewer than N points are connected:
   a) Pop the (cost, point) pair with the smallest cost from the heap.
   b) If the point is already visited, skip it (it was reached more cheaply earlier).
   c) Otherwise mark it visited, add its cost to `total_cost`, and increment the connected counter.
   d) For every unvisited point, push (manhattan distance from the new point, that point) onto the heap.
4) Return `total_cost`.

⚠️ Common Mistakes

• Forgetting to skip stale heap entries for points that were already visited, which double-counts edges and inflates the total.
• Using Euclidean distance instead of Manhattan distance for edge weights.
• Stopping after N - 1 heap pops rather than after N points are absorbed (the first pop has cost 0 and only seeds the tree).
• Trying to build and sort every pairwise edge up front when memory is tight — with N points that is O(N^2) edges, which Prim's with lazy edge generation avoids materializing all at once.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

def min_cost_connect_points(points):
    n = len(points)
    if n <= 1:
        return 0

    total_cost = 0
    connected = 0
    visited = [False] * n
    # Min-heap of (cost, point_index); start Prim's algorithm from point 0
    min_heap = [(0, 0)]

    while connected < n:
        cost, i = heapq.heappop(min_heap)
        if visited[i]:
            continue  # Stale entry: this point was already reached more cheaply

        # Add this point to the growing spanning tree
        visited[i] = True
        total_cost += cost
        connected += 1

        # Push the Manhattan-distance edge to every unvisited point
        x1, y1 = points[i]
        for j in range(n):
            if not visited[j]:
                x2, y2 = points[j]
                dist = abs(x1 - x2) + abs(y1 - y2)
                heapq.heappush(min_heap, (dist, j))

    return total_cost

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: points = 0, 0], [2, 2], [3, 10], [5, 2], [7, 0

  • Pop (0, point 0): absorb (0,0), total = 0. Push edges 4, 13, 7, 7 to the other points.
  • Pop (4, point 1): absorb (2,2), total = 4. Push edges 9, 3, 7.
  • Pop (3, point 3): absorb (5,2), total = 7. Push edges 10, 4.
  • Pop (4, point 4): absorb (7,0), total = 11. Push edge 14.
  • Skip stale entries (7, point 3), (7, point 4), (7, point 4) — those points are already in the tree. Pop (9, point 2): absorb (3,10), total = 20.
  • Output: 20

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

  • Pop (0, point 0): absorb (3,12), total = 0. Push edge 12 to (-2,5) and 18 to (-4,1).
  • Pop (12, point 1): absorb (-2,5), total = 12. Push edge 6 to (-4,1).
  • Pop (6, point 2): absorb (-4,1), total = 18.
  • Output: 18

• Input: points = 2, 3

  • Output: 0 (A single point needs no connections.)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of points.

• Time Complexity: O(N^2 log N) because each of the N absorbed points pushes up to N edges onto the heap, and each of the O(N^2) heap operations costs O(log N).
• Space Complexity: O(N^2) for the min-heap in the worst case, plus O(N) for the visited list. A classic array-based Prim's (tracking the best known distance per point) can bring this down to O(N) space and O(N^2) time, which is optimal for a dense complete graph.