Graphs crash course ↗ · 103

1584. Min Cost to Connect All Points

Build a minimum spanning tree on a complete graph where edge weights are Manhattan distances. Run Prim's algorithm with a min-heap: always grow the tree by the cheapest available edge, skipping nodes already inside.

● MediumPrim's MSTMin-Heap / Priority QueueGreedyTypeScript

PROBLEM What we're solving

Given n points on a 2-D plane, connect them all with the minimum total cost. The cost of connecting two points is their Manhattan distance: |x1 - x2| + |y1 - y2|. Each point must be reachable from every other (one connected component), and there are no required intermediate stops.

Worked example. points = [[0,0],[2,2],[3,10],[5,2],[7,0]]. The optimal MST uses edges with costs 4, 3, 5, and 6, totalling 20.

KEY IDEA It's a minimum spanning tree on a complete graph

Insight → any two points can be connected, so the graph is complete (every pair is an edge). The cheapest way to connect all nodes is the MST. Run Prim's algorithm: maintain a frontier, always pick the cheapest edge that adds a new node, and repeat until all nodes are inside. A min-heap keeps “find cheapest candidate” at O(log n).

RECIPE Prim's MST step by step

0 · Setup. Mark all nodes unvisited. Create a min-heap seeded with [cost=0, node=0]— zero cost to “include the starting node itself”.
1 · Pop cheapest. Extract [cost, u] from the heap. If u is already in the MST, this is a stale entry — skip it with continue.
2 · Commit. Mark u as in the MST, add cost to the running total. Increment the edge/node counter — stop when all n nodes are committed.
3 · Expand frontier. For every unvisited node v, compute the Manhattan distance from u to v and push [d, v]to the heap if it's cheaper than what we've seen before (optional optimisation — or push unconditionally and let the skip in step 1 handle duplicates).
4 · Return total. Once all nodes are in the MST, return totalCost.

Classic confusion → Prim's heap accumulates duplicate entries for the same node (each time a shorter path is discovered, we push again rather than decrease-key). The if (inMST[u]) continueguard in step 1 silently drops these stale pops — forget it and you'll add costs multiple times and loop forever.

COST Complexity & alternatives

Naive: try all spanning trees

O(n^n)

Exponential — hopeless for n > 10.

Prim's with a min-heap

O(n² log n)

n nodes × n neighbors each push, each push is O(log n). For a complete graph this is optimal.

Alternatives

Kruskal's algorithm sorts all O(n²) edges then applies Union-Find: O(n² log n)— same asymptotic but more memory. Kruskal shines when the graph is sparse; on this dense complete graph Prim's with an array-based “min edge” scan is actually O(n²) and preferred in practice.

Pattern transfer →Any time a problem asks you to “connect everything with minimum total edge cost” think MST. Variants: Network Delay Time (Dijkstra, single target), Connecting Cities With Minimum Cost(Kruskal with real edges given), Swim in Rising Water (MST/Dijkstra on a grid).

RUN IT Prim's MST on a complete graph

points (x,y separated by ;):

step 0 / 13

START5 points given. Start Prim's from node 0. Seed min-heap with [cost=0, node=0].

1function minCostConnectPoints(points: number[][]): number {
2▶  const n = points.length;
3  if (n <= 1) return 0;
4 
5  // inMST[i] = true once node i has been added to the spanning tree
6▶  const inMST = new Array<boolean>(n).fill(false);
7 
8  // minEdge[i] = cheapest known edge cost to connect node i into the MST
9▶  const minEdge = new Array<number>(n).fill(Infinity);
10▶  minEdge[0] = 0; // start from node 0 at cost 0
11 
12  // Min-heap entries: [cost, nodeIndex]
13  // Using a simple array-based binary heap
14▶  const heap: [number, number][] = [[0, 0]];
15▶  let totalCost = 0;
16▶  let edgesAdded = 0;
17 
18  const heapPush = (cost: number, node: number): void => {
19    heap.push([cost, node]);
20    let i = heap.length - 1;
21    while (i > 0) {
22      const p = (i - 1) >> 1;
23      if (heap[p][0] <= heap[i][0]) break;
24      [heap[p], heap[i]] = [heap[i], heap[p]];
25      i = p;
26    }
27  };
28 
29  const heapPop = (): [number, number] => {
30    const top = heap[0];
31    const last = heap.pop()!;
32    if (heap.length > 0) {
33      heap[0] = last;
34      let i = 0;
35      while (true) {
36        const l = 2 * i + 1, r = 2 * i + 2;
37        let s = i;
38        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
39        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
40        if (s === i) break;
41        [heap[i], heap[s]] = [heap[s], heap[i]];
42        i = s;
43      }
44    }
45    return top;
46  };
47 
48  while (heap.length > 0 && edgesAdded < n) {
49    const [cost, u] = heapPop();
50 
51    if (inMST[u]) continue; // stale heap entry — skip
52    inMST[u] = true;
53    totalCost += cost;
54    edgesAdded++;
55 
56    for (let v = 0; v < n; v++) {
57      if (!inMST[v]) {
58        const d = Math.abs(points[u][0] - points[v][0])
59                + Math.abs(points[u][1] - points[v][1]);
60        if (d < minEdge[v]) {
61          minEdge[v] = d;
62          heapPush(d, v);
63        }
64      }
65    }
66  }
67 
68  return totalCost;
69}

State

{}

inMST

{ 0:0, 1:inf, 2:inf, 3:inf, 4:inf }

minEdge

totalCost

edgesAdded

heap size

in MSTedge just addedcandidate edges / active nodeskipped (already in MST)minEdge per node

slowfast

TYPESCRIPT The solution, annotated

minCostConnectPoints.ts
function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  if (n <= 1) return 0;

  // inMST[i] = true once node i has been added to the spanning tree
  const inMST = new Array<boolean>(n).fill(false);

  // minEdge[i] = cheapest known edge cost to connect node i into the MST
  const minEdge = new Array<number>(n).fill(Infinity);
  minEdge[0] = 0; // start from node 0 at cost 0

  // Min-heap entries: [cost, nodeIndex]
  // Using a simple array-based binary heap
  const heap: [number, number][] = [[0, 0]];
  let totalCost = 0;
  let edgesAdded = 0;

  const heapPush = (cost: number, node: number): void => {
    heap.push([cost, node]);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };

  const heapPop = (): [number, number] => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]];
        i = s;
      }
    }
    return top;
  };

  while (heap.length > 0 && edgesAdded < n) {
    const [cost, u] = heapPop();

    if (inMST[u]) continue; // stale heap entry — skip
    inMST[u] = true;
    totalCost += cost;
    edgesAdded++;

    for (let v = 0; v < n; v++) {
      if (!inMST[v]) {
        const d = Math.abs(points[u][0] - points[v][0])
                + Math.abs(points[u][1] - points[v][1]);
        if (d < minEdge[v]) {
          minEdge[v] = d;
          heapPush(d, v);
        }
      }
    }
  }

  return totalCost;
}

Reading it block by block

Lines 3–8 — initialise MST state. inMST tracks which nodes are committed. minEdge caches the cheapest known edge into each node (used as an optional pruning guard). Seed the heap with [cost=0, node=0]— zero because we pay nothing to “reach the starting point from itself”.

Lines 10–30 — inline binary min-heap. JavaScript has no built-in priority queue, so we inline a binary heap. heapPush appends and bubbles up; heapPop swaps the root with the last element and sifts down. The invariant: heap[parent][0] ≤ heap[child][0] (min by cost).

Lines 33–37 — pop and skip stale entries. The heap may hold multiple entries for the same node (pushed at different distances). The if (inMST[u]) continue check is the core of the lazy-deletion pattern: once a node is committed, any later pops for it are discarded.

Lines 38–40 — commit the node. Mark u as in the MST, accumulate its edge cost, and increment edgesAdded. We stop as soon as all n nodes are added (a spanning tree on n nodes has exactly n-1 edges, but counting nodes is equivalent).

Lines 42–50 — expand the frontier. Iterate every non-MST node v, compute |x_u - x_v| + |y_u - y_v|, and push if it improves the best known cost for v. The if (d < minEdge[v]) guard avoids redundant heap entries and keeps the heap lean; it is optional but speeds up dense inputs.

Complexity → O(n² log n) time: for each of the n nodes committed we iterate n neighbors and push each in O(log n). O(n²) space in the worst case (all candidates in the heap). For this specific problem an O(n²) array-based Prim (no heap, linear scan for minimum) is also acceptable and keeps space at O(n).

INTERVIEWFollow-ups they'll ask

"Can you do O(n²) time instead?" Yes — replace the heap with a plain array minEdge[n] and do a linear scan to find the next cheapest node each round. Eliminates heap overhead; ideal for dense graphs.
"Why Prim's over Kruskal's here?"Kruskal's needs all O(n²)edges materialised and sorted first. Prim's discovers edges lazily, so memory stays O(n) (plus the heap).
"What if edge weights aren't Manhattan?"The algorithm is identical — just replace the distance formula. Prim's and Kruskal's work for any non-negative edge weight.
"Points on a grid — any special structure?"Manhattan distance on a grid lets you prune: the nearest Manhattan neighbour is never more than one “grid step” away. Some competitive-programming solutions exploit this to cut the graph to O(n log n) edges before running Kruskal's.
"What's the brute force?" Enumerate all spanning trees (n^(n-2)by Cayley's formula) and pick the minimum. Hopeless for n > 10.

MNEMONIC The one-liner

"Grow the tree one cheap edge at a time — always grab the nearest unvisited point from the frontier."

TRIGGERS When you see _ → reach for _

"connect all points / nodes with minimum total cost"	Prim's or Kruskal's MST
complete graph (every pair can connect)	Prim's with min-heap — no need to materialise all edges
growing a set greedily, always cheapest next	min-heap + inMST visited set
2-D points, Manhattan or Euclidean distance	MST with inline distance formula

SKELETON The reusable shape

skeleton.ts
const n = points.length;
const inMST = new Array<boolean>(n).fill(false);
const heap: [number, number][] = [[0, 0]]; // [cost, node]
let totalCost = 0, edgesAdded = 0;

while (heap.length > 0 && edgesAdded < n) {
  const [cost, u] = heapPop();
  if (inMST[u]) continue;
  inMST[u] = true;
  totalCost += cost;
  edgesAdded++;
  for (let v = 0; v < n; v++) {
    if (!inMST[v]) heapPush(manhattan(u, v), v);
  }
}
return totalCost;

FLASHCARDS Tap to flip

What algorithm solves 'connect all points minimum cost'?

Minimum Spanning Tree — Prim's (heap) or Kruskal's (sort + Union-Find).

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of Prim's algorithm with a min-heap on this problem?

QUESTION 02

points = [[0,0],[2,2],[3,10],[5,2],[7,0]]. What does the algorithm return?

QUESTION 03

Why does Prim's heap accumulate duplicate entries for the same node?

QUESTION 04

What is the guard that makes Prim's lazy-heap approach correct?

QUESTION 05

Manhattan distance between [1,3] and [4,7] is:

QUESTION 06

Why is Prim's preferred over Kruskal's for this problem?

QUESTION 07

When can you stop Prim's loop early?

QUESTION 08

#1584 · Min Cost to Connect All PointsPrim's MST on the fully connected graph of points with Manhattan-distance edge weights: a min-heap of (distance, point) greedily adds the cheapest reachable connection, summing the costs.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA It's a minimum spanning tree on a complete graph

RECIPE Prim's MST step by step

COST Complexity & alternatives

Alternatives

RUN IT Prim's MST on a complete graph

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _