1584. Min Cost to Connect All Points

Min Cost to Connect All Points (LeetCode 1584) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern.

• NeetCode 150 · #95 of 150 · Advanced Graphs
• NeetCode 250 · #167 of 250 · Advanced Graphs

How to solve Min Cost to Connect All Points

Min Cost to Connect All Points is a Minimum Spanning Tree problem, part of Graph Traversal Patterns (DFS & BFS). Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap.

Work towards the solution in these steps:

1. Consider modeling the points as nodes in a graph where edges represent the cost to connect two points.
2. Think about finding a subset of edges that connects all nodes with the minimum total cost, forming a tree without cycles.
3. Explore algorithms designed to find a Minimum Spanning Tree (MST), such as Prim's or Kruskal's algorithm, which are efficient for this type of problem.

The reference solution runs in O(n^2) time and O(n) space.

The Min Cost to Connect All Points solution and editorial walks through the full approach with reference code.

Problem statement

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.

Example 1: Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as shown above to get the minimum cost of 20.

Notice that there is a unique path between every pair of points.

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

Example 3: Input: points = [[0,0],[1,1],[1,0],[-1,1]] Output: 4

Example 4: Input: points = [[-1000000,-1000000],[1000000,1000000]] Output: 4000000

Example 5: Input: points = [[0,0]] Output: 0

Constraints: 1 <= points.length <= 1000 -106 <= xi, yi <= 106 All pairs (xi, yi) are distinct.

Topics and companies

Topics: Union Find.

Reported in interviews at Directi.

How to practise Min Cost to Connect All Points on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n) space.

Open Min Cost to Connect All Points in the code editor, or read the Min Cost to Connect All Points editorial for a worked solution with its approach and complexity analysis.

Where Min Cost to Connect All Points sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern
• The full DSA patterns sheet

Problems related to Min Cost to Connect All Points

Other problems that use the same Minimum Spanning Tree (Kruskal / Prim / DSU + heap) and Graph Traversal Patterns (DFS & BFS) techniques:

• Connecting Cities With Minimum Cost — Medium, same subpattern
• Optimize Water Distribution in a Village — Hard, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• All Paths from Source Lead to Destination — Medium, same pattern
• Build a Matrix With Conditions — Hard, same pattern

Min Cost to Connect All Points FAQ