This is one of those problems where the clean idea matters more than the amount of code. For 1584. Min Cost to Connect All Points, the solution in this repository is mainly a union-find solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: union-find, heap / priority queue, greedy.
The notes already sitting in the source point us in the right direction:
- priority_queue + dsu
- TLE
- 71 / 72 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are unite, isConnected, getDist, minCostConnectPoints, minnode.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//priority_queue + dsu
02//TLE
03//71 / 72 test cases passed.
04class DSU{
05public:
06 int n;
07 vector<int> parent;
08
09 DSU(int n){
10 this->n = n;
11 parent = vector<int>(n);
12 iota(parent.begin(), parent.end(), 0);
13 }
14
15 int find(int x){
16 if(parent[x] != x){
17 parent[x] = find(parent[x]);
18 }
19
20 return parent[x];
21 }
22
23 void unite(int x, int y){
24 int px = find(x);
25 int py = find(y);
26
27 parent[py] = px;
28 }
29
30 bool isConnected(int x, int y){
31 return (find(x) == find(y));
32 }
33};
34
35class Solution {
36public:
37 int getDist(vector<int>& pi, vector<int>& pj){
38 return abs(pi[0]-pj[0]) + abs(pi[1]-pj[1]);
39 }
40
41 int minCostConnectPoints(vector<vector<int>>& points) {
42 int n = points.size();
43
44 if(n == 1) return 0;
45
46
47 // vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
48
49 priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
50
51 for(int i = 0; i < n; ++i){
52 // graph[i][i] = 0;
53 vector<int>& pi = points[i];
54 for(int j = i+1; j < n; ++j){
55 vector<int>& pj = points[j];
56 int dist = getDist(pi, pj);
57 // graph[i][j] = graph[j][i] = dist;
58 pq.push({dist, i, j});
59 }
60 }
61
62 //edges needed
63 int need = n-1;
64 int ans = 0;
65 DSU dsu(n);
66
67 while(need > 0){
68 vector<int> edge = pq.top(); pq.pop();
69 int dist = edge[0], src = edge[1], dst = edge[2];
70
71 if(dsu.isConnected(src, dst))
72 continue;
73
74 dsu.unite(src, dst);
75 ans += dist;
76 --need;
77 }
78
79 return ans;
80 }
81};
82
83//Minimum spanning tree, Prim’s Algorithm
84//https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
85//https://www.geeksforgeeks.org/minimum-cost-connect-cities/
86//ARRAY
87//Runtime: 80 ms, faster than 100.00% of C++ online submissions for Min Cost to Connect All Points.
88//Memory Usage: 26.6 MB, less than 25.00% of C++ online submissions for Min Cost to Connect All Points.
89//vector
90//Runtime: 188 ms, faster than 50.00% of C++ online submissions for Min Cost to Connect All Points.
91//Memory Usage: 26.7 MB, less than 25.00% of C++ online submissions for Min Cost to Connect All Points.
92//time: O(V^2)
93#define ARRAY
94
95class Solution {
96public:
97 int getDist(vector<int>& pi, vector<int>& pj){
98 return abs(pi[0]-pj[0]) + abs(pi[1]-pj[1]);
99 }
100
101#ifdef ARRAY
102 int minnode(bool mstset[], int dist[], int n){
103#else
104 int minnode(vector<bool>& mstset, vector<int>& dist){
105 int n = mstset.size();
106#endif
107 int minv = INT_MAX;
108 int mini = -1;
109
110 for(int i = 0; i < n; ++i){
111 if(!mstset[i] && dist[i] < minv){
112 minv = dist[i];
113 mini = i;
114 }
115 }
116
117 return mini;
118 }
119
120 int primMST(vector<vector<int>>& graph){
121 int n = graph.size();
122
123
124#ifdef ARRAY
125 bool mstset[n];
126 int parent[n];
127 int dist[n];
128
129 //memset only work for char!
130 //it interpret its second argument as "unsigned char" and set n "bytes"!
131 // memset(mstset, false, n);
132 // memset(parent, -1, n);
133 // memset(dist, INT_MAX, n);
134 fill(mstset, mstset+n, false);
135 fill(parent, parent+n, -1);
136 fill(dist, dist+n, INT_MAX);
137#else
138 vector<bool> mstset(n, false); //whether is in MST
139 vector<int> parent(n, -1);
140 vector<int> dist(n, INT_MAX); //distance to MST
141#endif
142
143 // mstset[0] = true;
144 parent[0] = -1;
145 dist[0] = 0;
146
147 /*
148 in each iteration, we add one node into MST,
149 and then update dist and parent,
150 we only need to do n-1 iterations,
151 because for the last node, it won't update dist and parent
152 */
153 for(int i = 0; i < n-1; ++i){
154#ifdef ARRAY
155 int u = minnode(mstset, dist, n);
156#else
157 int u = minnode(mstset, dist);
158#endif
159
160 mstset[u] = true;
161
162 //update dist and parent with the newly added "u"
163 for(int v = 0; v < n; ++v){
164 //u and v are always connected in this problem
165 if(!mstset[v] && graph[u][v] < dist[v]){
166 dist[v] = graph[u][v];
167 parent[v] = u;
168 }
169 }
170 }
171
172 int cost = 0;
173 //note here i starts from 1
174 for(int i = 1; i < n; ++i){
175 cost += graph[parent[i]][i];
176 }
177
178 return cost;
179 }
180
181 int minCostConnectPoints(vector<vector<int>>& points) {
182 int n = points.size();
183
184 if(n == 1) return 0;
185
186 vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
187
188 for(int i = 0; i < n; ++i){
189 // graph[i][i] = 0;
190 vector<int>& pi = points[i];
191 for(int j = i+1; j < n; ++j){
192 vector<int>& pj = points[j];
193 int dist = getDist(pi, pj);
194 graph[i][j] = graph[j][i] = dist;
195 }
196 }
197
198 return primMST(graph);
199 }
200};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.