LeetCode 952: Largest Component Size by Common Factor

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

Given a non-empty array of unique positive integers A, consider the following graph:

• There are nums.length nodes, labeled nums[0] to nums[nums.length - 1];

• There is an edge between nums[i] and nums[j] if and only if nums[i] and nums[j] share a common factor greater than 1.

• Return the size of the largest connected component in the graph.

Example 1:

• Input: [4,6,15,35]
• Output: 4

enter image description here

Example 2:

• Input: [20,50,9,63]
• Output: 2

enter image description here

Example 3:

• Input: [2,3,6,7,4,12,21,39]
• Output: 8

enter image description here

Note:

• \1ドル <= nums.length <= 20000\$
• \1ドル <= nums[i] <= 100000\$

Inputs

[4,6,15,35]
[20,50,9,63]
[2,3,6,7,4,12,21,39]
[2,3,6,7,4,12,21,39,100,101,102,103,104,1200,123,123,13424]

Outputs

4
2
8
15

Code

#include <cstdint>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#define max(a, b) (a > b ? a : b) // std::max(a, b)
// Union Find
struct DisjointSets {
 DisjointSets(int_fast64_t n) : parent(n) {
 for (int_fast64_t index = 0; index < n; index++) {
 parent[index] = index;
 }
 }
 void union_ds(const int_fast64_t x, const int_fast64_t y) {
 parent[find_ds(x)] = parent[find_ds(y)];
 }
 const int_fast64_t find_ds(const int_fast64_t x) {
 if (parent[x] != x) {
 parent[x] = find_ds(parent[x]);
 }
 return parent[x];
 }
private:
 std::vector<int> parent;
};
struct Solution {
 static const size_t largestComponentSize(const std::vector<int> &nums) {
 const size_t max_nums = *std::max_element(nums.begin(), nums.end());
 DisjointSets union_find(max_nums + 1);
 for (const auto &num : nums) {
 for (size_t k = 2; k <= std::sqrt(num); k++) {
 if (num % k == 0) {
 union_find.union_ds(num, k);
 union_find.union_ds(num, num / k);
 }
 }
 }
 std::unordered_map<int, int> component_map;
 size_t largest_component = 1;
 for (const auto &num : nums) {
 size_t curr_component = ++component_map[union_find.find_ds(num)];
 largest_component = max(largest_component, curr_component);
 }
 return largest_component;
 }
};

References

• Problem

• Discuss

• Solution

• Union Find

Answer 1

Observation

I don't understand your solution.

Code Review

#define max(a, b) (a > b ? a : b) // std::max(a, b)

Don't do this. Use std::max() directly.

Long gone are the days that we used macros to inline code like this. The std::max() will work correctly in all situations; this macro has edge cases that will fail (especially if a and b are not just simple numbers).

---

The size_t is coming because you included a C header file cstdint. It is not guaranteed to be in the global namespace (it commonly is but its not guaranteed). So prefer to use std::size_t.

 const std::size_t max_nums = *std::max_element(nums.begin(), nums.end());

• Toby Speight: Also, std::int_fast64_t is being assumed in global namespace; that's as non-portable is unqualified size_t.