The trick here is to name the state correctly, then let the implementation follow. For 952. Largest Component Size by Common Factor, the solution in this repository is mainly a union-find solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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, graph traversal.
The notes already sitting in the source point us in the right direction:
- Graph, BFS
- TLE
- 71 / 100 test cases passed.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are gcd, largestComponentSize, visited, unite, SieveOfEratosthenes.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- 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:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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//Graph, BFS
02//TLE
03//71 / 100 test cases passed.
04class Solution {
05public:
06 int gcd(int x, int y){
07 if(x < y){
08 swap(x, y);
09 }
10
11 if(y == 0){
12 return x;
13 }
14
15 return gcd(y, x%y);
16 };
17
18 int largestComponentSize(vector<int>& A) {
19 int ans = 0;
20
21 int n = A.size();
22
23 unordered_map<int, unordered_set<int>> graph;
24
25 for(int i = 0; i < n; ++i){
26 for(int j = i+1; j < n; ++j){
27 if(gcd(A[i], A[j]) > 1){
28 graph[i].insert(j);
29 graph[j].insert(i);
30 }
31 }
32 }
33
34 vector<bool> visited(n, false);
35
36 for(int i = 0; i < n; ++i){
37 if(visited[i]) continue;
38
39 int comp_size = 0;
40
41 queue<int> q;
42 q.push(i);
43 visited[i] = true;
44
45 while(!q.empty()){
46 int cur = q.front(); q.pop();
47 ++comp_size;
48
49 for(int nei : graph[cur]){
50 if(!visited[nei]){
51 visited[nei] = true;
52 q.push(nei);
53 }
54 }
55 }
56
57 ans = max(ans, comp_size);
58 }
59
60 return ans;
61 }
62};
63
64//Union find
65//TLE
66//74 / 100 test cases passed.
67class DSU{
68public:
69 vector<int> parent;
70
71 DSU(int n){
72 parent = vector<int>(n, 0);
73 iota(parent.begin(), parent.end(), 0);
74 }
75
76 int find(int x){
77 if(parent[x] != x){
78 parent[x] = find(parent[x]);
79 }
80
81 return parent[x];
82 }
83
84 void unite(int x, int y){
85 //merge the larger to the smaller
86 parent[find(y)] = find(x);
87 }
88};
89
90class Solution {
91public:
92 int gcd(int x, int y){
93 if(x < y) swap(x, y);
94 if(y == 0) return x;
95 return gcd(y, x%y);
96 };
97
98 int largestComponentSize(vector<int>& A) {
99 int n = A.size();
100
101 DSU dsu(n);
102
103 for(int i = 0; i < n; ++i){
104 for(int j = i+1; j < n; ++j){
105 if(gcd(A[i], A[j]) > 1){
106 dsu.unite(i, j);
107 }
108 }
109 }
110
111 unordered_map<int, int> group2count;
112 int ans = 0;
113
114 for(int i = 0; i < n; ++i){
115 ++group2count[dsu.find(i)];
116 ans = max(ans, group2count[dsu.find(i)]);
117 }
118
119 return ans;
120 }
121};
122
123//Union find + precompute prime numbers
124//https://www.geeksforgeeks.org/sieve-of-eratosthenes/
125//TLE
126//78 / 100 test cases passed.
127class DSU{
128public:
129 vector<int> parent;
130
131 DSU(int n){
132 parent = vector<int>(n, 0);
133 iota(parent.begin(), parent.end(), 0);
134 }
135
136 int find(int x){
137 if(parent[x] != x){
138 parent[x] = find(parent[x]);
139 }
140
141 return parent[x];
142 }
143
144 void unite(int x, int y){
145 //merge the larger to the smaller
146 parent[find(y)] = find(x);
147 }
148};
149
150class Solution {
151public:
152 vector<bool> isprime;
153
154 void SieveOfEratosthenes(int n){
155 for(int p=2; p*p<=n; p++){
156 if(isprime[p]){
157 for(int i=p*p; i<=n; i += p)
158 isprime[i] = false;
159 }
160 }
161 };
162
163 int largestComponentSize(vector<int>& A) {
164 int n = A.size();
165
166 int max_ele = *max_element(A.begin(), A.end());
167 isprime = vector<bool>(max_ele+1, true);
168 SieveOfEratosthenes(max_ele);
169
170 // cout << "max: " << max_ele << endl;
171
172 unordered_set<int> primes;
173 for(int p = 2; p <= max_ele; ++p){
174 if(isprime[p]){
175 primes.insert(p);
176 }
177 }
178
179 DSU dsu(max_ele+1);
180
181 for(int p : primes){
182 for(int i = 0; i < n; ++i){
183 if(A[i]%p == 0){
184 dsu.unite(p, A[i]);
185 }
186 }
187 }
188
189 unordered_map<int, int> group2count;
190 int ans = 0;
191
192 for(int i = 0; i < n; ++i){
193 ++group2count[dsu.find(A[i])];
194 ans = max(ans, group2count[dsu.find(A[i])]);
195 }
196
197 return ans;
198 }
199};
200
201//Union find + a map to memorize what index to be united
202//https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/200959/Simplest-Solution-(Union-Find-only)-No-Prime-Calculation
203//Runtime: 992 ms, faster than 12.23% of C++ online submissions for Largest Component Size by Common Factor.
204//Memory Usage: 42.4 MB, less than 51.44% of C++ online submissions for Largest Component Size by Common Factor.
205class DSU{
206public:
207 int maxsz;
208 vector<int> parent;
209 vector<int> sz;
210
211 DSU(int n){
212 maxsz = 0;
213 parent = vector<int>(n, 0);
214 iota(parent.begin(), parent.end(), 0);
215 sz = vector<int>(n, 1);
216 }
217
218 int find(int x){
219 if(parent[x] != x){
220 parent[x] = find(parent[x]);
221 }
222
223 return parent[x];
224 }
225
226 void unite(int x, int y){
227 //merge the larger to the smaller
228 int rx = find(x);
229 int ry = find(y);
230
231 //this line is important!
232 if(rx == ry) return;
233
234 if(sz[rx] > sz[ry]){
235 //merge y into x
236 parent[ry] = rx;
237 //only care the large union's size
238 sz[rx] += sz[ry];
239 maxsz = max(maxsz, sz[rx]);
240 }else{
241 parent[rx] = ry;
242 //only care the large union's size
243 sz[ry] += sz[rx];
244 maxsz = max(maxsz, sz[ry]);
245 }
246 }
247};
248
249class Solution {
250public:
251 int largestComponentSize(vector<int>& A) {
252 int n = A.size();
253
254 DSU dsu(n);
255 unordered_map<int, int> fact2idx;
256
257 for(int i = 0; i < n; ++i){
258 for(int factor = 2; factor*factor <= A[i]; ++factor){
259 if(A[i]%factor == 0){
260 if(fact2idx.find(factor) != fact2idx.end()){
261 dsu.unite(i, fact2idx[factor]);
262 }else{
263 fact2idx[factor] = i;
264 }
265 int factor2 = A[i]/factor;
266 if(fact2idx.find(factor2) != fact2idx.end()){
267 dsu.unite(i, fact2idx[factor2]);
268 }else{
269 fact2idx[factor2] = i;
270 }
271 }
272 }
273 //A[i] is itself's factor
274 if(fact2idx.find(A[i]) != fact2idx.end()){
275 dsu.unite(i, fact2idx[A[i]]);
276 }else{
277 fact2idx[A[i]] = i;
278 }
279 }
280
281 return dsu.maxsz;
282 }
283};
284
285//Union find + a map to memorize what index to be united + precompute primes
286//https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/200546/Prime-Factorization-and-Union-Find
287//TLE
288//81 / 100 test cases passed.
289class DSU{
290public:
291 int maxsz;
292 vector<int> parent;
293 vector<int> sz;
294
295 DSU(int n){
296 maxsz = 0;
297 parent = vector<int>(n, 0);
298 iota(parent.begin(), parent.end(), 0);
299 sz = vector<int>(n, 1);
300 }
301
302 int find(int x){
303 if(parent[x] != x){
304 parent[x] = find(parent[x]);
305 }
306
307 return parent[x];
308 }
309
310 void unite(int x, int y){
311 //merge the larger to the smaller
312 int rx = find(x);
313 int ry = find(y);
314
315 //this line is important!
316 if(rx == ry) return;
317
318 if(sz[rx] > sz[ry]){
319 //merge y into x
320 parent[ry] = rx;
321 //only care the large union's size
322 sz[rx] += sz[ry];
323 maxsz = max(maxsz, sz[rx]);
324 }else{
325 parent[rx] = ry;
326 //only care the large union's size
327 sz[ry] += sz[rx];
328 maxsz = max(maxsz, sz[ry]);
329 }
330 }
331};
332
333class Solution {
334public:
335 vector<bool> isprime;
336 set<int> primes;
337
338 void SieveOfEratosthenes(int n){
339 for(int p=2; p<=n; p++){
340 if(isprime[p]){
341 primes.insert(p);
342 for(int i=2; p*i<=n; i++)
343 isprime[p*i] = false;
344 }
345 }
346 };
347
348 int largestComponentSize(vector<int>& A) {
349 int n = A.size();
350
351 int max_ele = *max_element(A.begin(), A.end());
352 isprime = vector<bool>(max_ele+1, true);
353 SieveOfEratosthenes(max_ele);
354
355 // cout << "max: " << max_ele << endl;
356
357 DSU dsu(n);
358 unordered_map<int, int> prime2idx;
359
360 for(int i = 0; i < n; ++i){
361 for(int p : primes){
362 if(A[i]%p == 0){
363 if(primes.find(A[i]) != primes.end()){
364 p = A[i];
365 }
366 if(prime2idx.find(p) != prime2idx.end()){
367 dsu.unite(i, prime2idx[p]);
368 }else{
369 prime2idx[p] = i;
370 }
371
372 while(A[i]%p == 0){
373 A[i] /= p;
374 }
375 }
376
377 if(A[i] == 1) break;
378 }
379 }
380
381 return dsu.maxsz;
382 }
383};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.