1584. Min Cost to Connect All Points

At a Glance

Topic: graphs
Pattern: MST — Prim / Kruskal (shortest-path / spanning-tree family)
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: High
LeetCode: 1584

Problem (one-liner)

Given 2D integer points, cost between any pair is Manhattan distance. Return minimum total edge weight to make graph connected (spanning tree).

Recognition Cues

Complete graph implicit — too many edges to materialize all
MST — Prim grows tree with min edge to frontier; Kruskal sorts edges

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

All pairs edges + Kruskal — O(n^2 log n) with sorting.
Optimal — Prim with lazy heap — O(n^2 log n) similar; O(n^2) possible with clever nearest arrays.

Optimal Solution

Go

import (
	"container/heap"
)

type primEdge struct {
	point    int
	distance int
}

type primHeap []primEdge

func (heapSlice primHeap) Len() int { return len(heapSlice) }
func (heapSlice primHeap) Less(left, right int) bool {
	return heapSlice[left].distance < heapSlice[right].distance
}
func (heapSlice primHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *primHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(primEdge))
}

func (heapSlice *primHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	item := old[length-1]
	*heapSlice = old[0 : length-1]
	return item
}

func manhattan(left []int, right []int) int {
	dx := left[0] - right[0]
	dy := left[1] - right[1]
	if dx < 0 {
		dx = -dx
	}
	if dy < 0 {
		dy = -dy
	}
	return dx + dy
}

func minCostConnectPoints(points [][]int) int {
	nodeCount := len(points)
	visited := make([]bool, nodeCount)
	minHeap := &primHeap{}
	heap.Init(minHeap)
	heap.Push(minHeap, primEdge{point: 0, distance: 0})
	total := 0
	edgesUsed := 0

	for minHeap.Len() > 0 && edgesUsed < nodeCount {
		current := heap.Pop(minHeap).(primEdge)
		if visited[current.point] {
			continue
		}
		visited[current.point] = true
		total += current.distance
		edgesUsed++
		for neighbor := 0; neighbor < nodeCount; neighbor++ {
			if visited[neighbor] {
				continue
			}
			distance := manhattan(points[current.point], points[neighbor])
			heap.Push(minHeap, primEdge{point: neighbor, distance: distance})
		}
	}
	return total
}

JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index].distance >= this.data[parentIndex].distance) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let smallest = index;
      if (leftChild < length && this.data[leftChild].distance < this.data[smallest].distance) {
        smallest = leftChild;
      }
      if (rightChild < length && this.data[rightChild].distance < this.data[smallest].distance) {
        smallest = rightChild;
      }
      if (smallest === index) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function manhattan(left, right) {
  return Math.abs(left[0] - right[0]) + Math.abs(left[1] - right[1]);
}

function minCostConnectPoints(points) {
  const nodeCount = points.length;
  const visited = new Array(nodeCount).fill(false);
  const heap = new MinHeap();
  heap.push({ point: 0, distance: 0 });
  let total = 0;
  let edgesUsed = 0;

  while (heap.size() > 0 && edgesUsed < nodeCount) {
    const current = heap.pop();
    if (visited[current.point]) {
      continue;
    }
    visited[current.point] = true;
    total += current.distance;
    edgesUsed += 1;
    for (let neighbor = 0; neighbor < nodeCount; neighbor += 1) {
      if (visited[neighbor]) {
        continue;
      }
      const distance = manhattan(points[current.point], points[neighbor]);
      heap.push({ point: neighbor, distance });
    }
  }
  return total;
}