Skip to main content

1584. Min Cost to Connect All Points

medium

Given points in a plane with Manhattan-distance edges, return the minimum cost to connect them all. The textbook Minimum Spanning Tree problem — Prim's with a heap or Kruskal's with Union-Find both work.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Connecting n points with minimum total cost = Minimum Spanning Tree.

Hint 2

Prim's: start from any point, repeatedly add the cheapest edge connecting the visited set to an unvisited point. Use a min-heap of (cost, point).

Hint 3

Kruskal's: sort all O(n^2) edges by cost, then union endpoints; accept the edge if it connects two different components, until n-1 edges accepted.

Solution approach

Reveal approach

Prim's MST. Start from point 0; maintain a min-heap seeded with (0, 0) (cost, point_index) and a visited set. Repeatedly pop the smallest (d, u): if u is already visited, skip; else add d to total and mark u visited. For every unvisited v, push (manhattan(u, v), v) onto the heap. Stop when visited.size == n. Return total. The heap eventually holds O(n^2) entries (every cross-edge), but we only pop n times. The 'skip if visited' guard keeps things correct. O(n^2 log n) with heap-based Prim's. Kruskal's alternative: generate all n*(n-1)/2 edges, sort, then Union-Find — clean and slightly faster for sparse graphs but slower for dense.

Complexity

Time
O(n^2 log n)
Space
O(n^2)

Related patterns

  • minimum-spanning-tree
  • prims
  • kruskals
  • union-find
  • heap

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Min Cost to Connect All Points and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →