What is the brute force approach and complexity for Min Cost to Connect All Points?

Grow the tree one point at a time, scanning every (inside, outside) pair each round with time complexity O(N³) and space complexity O(N).

How do you identify the pattern for Min Cost to Connect All Points?

Look for key signals in the prompt: "minimum cost to link all points" indicates A minimum spanning tree: n − 1 links, no loop, the smallest total.; "Manhattan distance between points" indicates No edge list is given: every pair of points is a possible link, a complete graph with n(n − 1) / 2 edges.; "exactly one path between any two points" indicates The chosen links must form a tree: connected and without a cycle..

Min Cost to Connect All Points

Medium·LeetCode #1584 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given n points on a 2D plane, where points[i] = [xᵢ, yᵢ].

Link the points so that every point can reach every other point through exactly one path. The cost of linking two points is their Manhattan distance: |xᵢ − xⱼ| + |yᵢ − yⱼ|. Any two points can be linked, so every pair is a possible link.

Return the minimum total cost to link all the points.

Input

points, a list of [x, y] coordinates.

Output

A single integer: the minimum total cost to link all the points.

Example 1

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

Output: 20

Link 0–1 (4), 1–3 (3), 3–4 (4) and 1–2 (9). That is 4 + 3 + 4 + 9 = 20, and no cheaper set of links reaches every point.

Example 2

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

Output: 18

Link points 2 and 1 (cost 6) and points 0 and 1 (cost 12). That is 6 + 12 = 18.

Constraints

• 1 ≤ points.length ≤ 1000
• −10^6 ≤ xᵢ, yᵢ ≤ 10^6
• All points are distinct.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum cost to link all points”

→ A minimum spanning tree: n − 1 links, no loop, the smallest total.

“Manhattan distance between points”

→ No edge list is given: every pair of points is a possible link, a complete graph with n(n − 1) / 2 edges.

“exactly one path between any two points”

→ The chosen links must form a tree: connected and without a cycle.

Approach Complexity Ladder

Brute Force — naive Prim: rescan every pair each roundO(N³)O(N)

Grow the tree one point at a time, scanning every (inside, outside) pair each round

Better — Kruskal on all pairsO(N² log N)O(N²)

List every pair as an edge, sort them once, keep a pair only if its points are in different groups

Optimal — Prim with a dist arrayO(N²)O(N)

Keep dist[j], the cheapest link from the tree to point j; each round adds the minimum and updates only that point's links

Brute Force Intuition

Start the tree at point 0. In each of the n − 1 rounds, scan every pair where one point is in the tree and the other is outside. Add the outside point of the cheapest pair, and add its cost to the total.

Recognition rule for this sub-pattern:

Sort edges by cost; take an edge only if it joins two different groups.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture