Welcome to Subscribe On Youtube
1584. Min Cost to Connect All Points
Description
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
Constraints:
1 <= points.length <= 1000-106 <= xi, yi <= 106- All pairs
(xi, yi)are distinct.
Solutions
Solution 1: Direct Implementation
We define an array $dist$, where $dist[i]$ represents the distance from the point $i$ to the current spanning tree. Initially, it is $dist[0] = 0$, and the rest are $+\infty$. We define an array $vis$, where $vis[i]$ represents the point $i$. Whether in the spanning tree, initially all points are not in the spanning tree. Define a two-dimensional array $g$, where $g[i][j]$ represents the distance from point $i$ to point $j$. Then our goal is to add all points to the spanning tree with the minimum total cost.
Each time we select a point $i$ with the smallest distance from the points that are not in the spanning tree, add the point $i$ to the spanning tree, and update the distance from $i$ to other points into the $dist$ array until all points are in the spanning tree.
This algorithm is suitable for dense graphs, with time complexity $O(n^2)$ and space complexity $O(n^2)$. Where $n$ is the number of points.
Solution 2
We first sort all the edges from small to large in length, loop through each edge, and add them to the graph one by one. When all points reach a connected state, exit the loop and return the total cost at this time.
Time complexity $O(m \times \log m)$, space complexity $O(m)$. Among them, $m$ is the number of edges, in this question $m = n^2$.
-
class Solution { public int minCostConnectPoints(int[][] points) { final int inf = 1 << 30; int n = points.length; int[][] g = new int[n][n]; for (int i = 0; i < n; ++i) { int x1 = points[i][0], y1 = points[i][1]; for (int j = i + 1; j < n; ++j) { int x2 = points[j][0], y2 = points[j][1]; int t = Math.abs(x1 - x2) + Math.abs(y1 - y2); g[i][j] = t; g[j][i] = t; } } int[] dist = new int[n]; boolean[] vis = new boolean[n]; Arrays.fill(dist, inf); dist[0] = 0; int ans = 0; for (int i = 0; i < n; ++i) { int j = -1; for (int k = 0; k < n; ++k) { if (!vis[k] && (j == -1 || dist[k] < dist[j])) { j = k; } } vis[j] = true; ans += dist[j]; for (int k = 0; k < n; ++k) { if (!vis[k]) { dist[k] = Math.min(dist[k], g[j][k]); } } } return ans; } } // Solution 2 class Solution { private int[] p; public int minCostConnectPoints(int[][] points) { int n = points.length; List<int[]> g = new ArrayList<>(); for (int i = 0; i < n; ++i) { int x1 = points[i][0], y1 = points[i][1]; for (int j = i + 1; j < n; ++j) { int x2 = points[j][0], y2 = points[j][1]; g.add(new int[] {Math.abs(x1 - x2) + Math.abs(y1 - y2), i, j}); } } g.sort(Comparator.comparingInt(a -> a[0])); p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } int ans = 0; for (int[] e : g) { int cost = e[0], i = e[1], j = e[2]; if (find(i) == find(j)) { continue; } p[find(i)] = find(j); ans += cost; if (--n == 1) { return ans; } } return 0; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
class Solution { public: int minCostConnectPoints(vector<vector<int>>& points) { int n = points.size(); int g[n][n]; for (int i = 0; i < n; ++i) { int x1 = points[i][0], y1 = points[i][1]; for (int j = i + 1; j < n; ++j) { int x2 = points[j][0], y2 = points[j][1]; int t = abs(x1 - x2) + abs(y1 - y2); g[i][j] = t; g[j][i] = t; } } int dist[n]; bool vis[n]; memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[0] = 0; int ans = 0; for (int i = 0; i < n; ++i) { int j = -1; for (int k = 0; k < n; ++k) { if (!vis[k] && (j == -1 || dist[k] < dist[j])) { j = k; } } vis[j] = true; ans += dist[j]; for (int k = 0; k < n; ++k) { if (!vis[k]) { dist[k] = min(dist[k], g[j][k]); } } } return ans; } }; // Solution 2 class Solution { public: vector<int> p; int minCostConnectPoints(vector<vector<int>>& points) { int n = points.size(); vector<vector<int>> g; for (int i = 0; i < n; ++i) { int x1 = points[i][0], y1 = points[i][1]; for (int j = i + 1; j < n; ++j) { int x2 = points[j][0], y2 = points[j][1]; g.push_back({abs(x1 - x2) + abs(y1 - y2), i, j}); } } sort(g.begin(), g.end()); p.resize(n); for (int i = 0; i < n; ++i) p[i] = i; int ans = 0; for (auto& e : g) { int cost = e[0], i = e[1], j = e[2]; if (find(i) == find(j)) continue; p[find(i)] = find(j); ans += cost; if (--n == 1) return ans; } return 0; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } }; -
class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: n = len(points) g = [[0] * n for _ in range(n)] dist = [inf] * n vis = [False] * n for i, (x1, y1) in enumerate(points): for j in range(i + 1, n): x2, y2 = points[j] t = abs(x1 - x2) + abs(y1 - y2) g[i][j] = g[j][i] = t dist[0] = 0 ans = 0 for _ in range(n): i = -1 for j in range(n): if not vis[j] and (i == -1 or dist[j] < dist[i]): i = j vis[i] = True ans += dist[i] for j in range(n): if not vis[j]: dist[j] = min(dist[j], g[i][j]) return ans # Solution 2 class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(points) g = [] for i, (x1, y1) in enumerate(points): for j in range(i + 1, n): x2, y2 = points[j] t = abs(x1 - x2) + abs(y1 - y2) g.append((t, i, j)) p = list(range(n)) ans = 0 for cost, i, j in sorted(g): pa, pb = find(i), find(j) if pa == pb: continue p[pa] = pb ans += cost n -= 1 if n == 1: break return ans -
func minCostConnectPoints(points [][]int) (ans int) { n := len(points) g := make([][]int, n) vis := make([]bool, n) dist := make([]int, n) for i := range g { g[i] = make([]int, n) dist[i] = 1 << 30 } for i := range g { x1, y1 := points[i][0], points[i][1] for j := i + 1; j < n; j++ { x2, y2 := points[j][0], points[j][1] t := abs(x1-x2) + abs(y1-y2) g[i][j] = t g[j][i] = t } } dist[0] = 0 for i := 0; i < n; i++ { j := -1 for k := 0; k < n; k++ { if !vis[k] && (j == -1 || dist[k] < dist[j]) { j = k } } vis[j] = true ans += dist[j] for k := 0; k < n; k++ { if !vis[k] { dist[k] = min(dist[k], g[j][k]) } } } return } func abs(x int) int { if x < 0 { return -x } return x } // Solution 2 func minCostConnectPoints(points [][]int) int { n := len(points) var g [][]int for i, p := range points { x1, y1 := p[0], p[1] for j := i + 1; j < n; j++ { x2, y2 := points[j][0], points[j][1] g = append(g, []int{abs(x1-x2) + abs(y1-y2), i, j}) } } sort.Slice(g, func(i, j int) bool { return g[i][0] < g[j][0] }) ans := 0 p := make([]int, n) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, e := range g { cost, i, j := e[0], e[1], e[2] if find(i) == find(j) { continue } p[find(i)] = find(j) ans += cost n-- if n == 1 { return ans } } return 0 } func abs(x int) int { if x < 0 { return -x } return x } -
function minCostConnectPoints(points: number[][]): number { const n = points.length; const g: number[][] = Array(n) .fill(0) .map(() => Array(n).fill(0)); const dist: number[] = Array(n).fill(1 << 30); const vis: boolean[] = Array(n).fill(false); for (let i = 0; i < n; ++i) { const [x1, y1] = points[i]; for (let j = i + 1; j < n; ++j) { const [x2, y2] = points[j]; const t = Math.abs(x1 - x2) + Math.abs(y1 - y2); g[i][j] = t; g[j][i] = t; } } let ans = 0; dist[0] = 0; for (let i = 0; i < n; ++i) { let j = -1; for (let k = 0; k < n; ++k) { if (!vis[k] && (j === -1 || dist[k] < dist[j])) { j = k; } } vis[j] = true; ans += dist[j]; for (let k = 0; k < n; ++k) { if (!vis[k]) { dist[k] = Math.min(dist[k], g[j][k]); } } } return ans; }