Katkat
Back

Connect Points With Minimum Total Distance

ByteDanceData Engineer · Onsite
MediumData EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a geometric optimization task as a Minimum Spanning Tree (MST) problem and implement it efficiently using Kruskal's or Prim's algorithm.

Problem Statement

You are given a list of 2D coordinates points representing locations on a grid. You need to connect all points such that there is exactly one path between any two points. The cost of connecting two points (x1, y1) and (x2, y2) is defined by their Manhattan distance: |x1 - x2| + |y1 - y2|.

Your goal is to find the minimum total cost to connect all points.

Implement the function min_cost_connect_points(points: List[List[int]]) -> int.

Constraints

  • 1 <= points.length <= 1000
  • -10^6 <= xi, yi <= 10^6

Examples

Example 1: Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: Connecting these points using an MST structure results in a total distance of 20.

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

Edge Cases

  • Single point (cost should be 0).
  • Points with identical coordinates.
  • Large coordinates where distance calculation might overflow if not handled (though Python handles large integers automatically).

Hints

Hint 1

Treat the points as nodes in a complete graph where the edge weight between any two nodes is their Manhattan distance.

Hint 2

Since this is a classic Minimum Spanning Tree problem, consider using Kruskal's or Prim's algorithm.

Hint 3

Given that the graph is dense (every point connected to every other point), Prim's algorithm with an adjacency matrix or a priority queue will be more efficient than Kruskal's.

Follow-up questions

  • How does the complexity change if the distance metric is changed to Euclidean distance?
  • If the number of points increases to 100,000, why would the current approach fail and what alternative spatial partitioning data structures (like KD-trees) could help?
  • Can you explain the trade-offs between using Prim's algorithm versus Kruskal's algorithm in terms of space and time complexity for this specific input size?