1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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 situation this macro has edge cased that will fail (especially if a or 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 size_t max_nums = *std::max_element(nums.begin(), nums.end());
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.