2584. Split the Array to Make Coprime Products

• Time: $O(n\sqrt{n})$
• Space: $O(n\sqrt{n})$

C++JavaPython

class Solution {
 public:
  int findValidSplit(vector<int>& nums) {
    unordered_map<int, int> leftPrimeFactors;
    unordered_map<int, int> rightPrimeFactors;

    for (const int num : nums)
      for (const int primeFactor : getPrimeFactors(num))
        ++rightPrimeFactors[primeFactor];

    for (int i = 0; i < nums.size() - 1; ++i) {
      for (const int primeFactor : getPrimeFactors(nums[i])) {
        if (--rightPrimeFactors[primeFactor] == 0) {
          // rightPrimeFactors[primeFactor] == 0, so no need to track
          // leftPrimeFactors[primeFactor].
          rightPrimeFactors.erase(primeFactor);
          leftPrimeFactors.erase(primeFactor);
        } else {
          // Otherwise, need to track leftPrimeFactors[primeFactor].
          ++leftPrimeFactors[primeFactor];
        }
      }
      if (leftPrimeFactors.empty())
        return i;
    }

    return -1;
  }

 private:
  // Gets the prime factors under sqrt(10^6).
  vector<int> getPrimeFactors(int num) {
    vector<int> primeFactors;
    for (int divisor = 2; divisor <= min(1000, num); ++divisor)
      if (num % divisor == 0) {
        primeFactors.push_back(divisor);
        while (num % divisor == 0)
          num /= divisor;
      }
    // Handle the case that `num` contains a prime factor > 1000.
    if (num > 1)
      primeFactors.push_back(num);
    return primeFactors;
  }
};

class Solution {
  public int findValidSplit(int[] nums) {
    Map<Integer, Integer> leftPrimeFactors = new HashMap<>();
    Map<Integer, Integer> rightPrimeFactors = new HashMap<>();

    for (final int num : nums)
      for (final int primeFactor : getPrimeFactors(num))
        rightPrimeFactors.merge(primeFactor, 1, Integer::sum);

    for (int i = 0; i < nums.length - 1; ++i) {
      for (final int primeFactor : getPrimeFactors(nums[i])) {
        rightPrimeFactors.merge(primeFactor, -1, Integer::sum);
        if (rightPrimeFactors.get(primeFactor) == 0) {
          // rightPrimeFactors[primeFactor] == 0, so no need to track
          // leftPrimeFactors[primeFactor].
          rightPrimeFactors.remove(primeFactor);
          leftPrimeFactors.remove(primeFactor);
        } else {
          // Otherwise, need to track leftPrimeFactors[primeFactor].
          leftPrimeFactors.merge(primeFactor, 1, Integer::sum);
        }
      }
      if (leftPrimeFactors.isEmpty())
        return i;
    }

    return -1;
  }

  // Gets the prime factors under sqrt(10^6).
  private List<Integer> getPrimeFactors(int num) {
    List<Integer> primeFactors = new ArrayList<>();
    for (int divisor = 2; divisor <= Math.min(1000, num); ++divisor)
      if (num % divisor == 0) {
        primeFactors.add(divisor);
        while (num % divisor == 0)
          num /= divisor;
      }
    // Handle the case that `num` contains a prime factor > 1000.
    if (num > 1)
      primeFactors.add(num);
    return primeFactors;
  }
}

class Solution:
  def findValidSplit(self, nums: List[int]) -> int:
    leftPrimeFactors = collections.Counter()
    rightPrimeFactors = collections.Counter()

    def getPrimeFactors(num: int) -> List[int]:
      """Gets the prime factors under sqrt(10^6)."""
      primeFactors = []
      for divisor in range(2, min(1000, num) + 1):
        if num % divisor == 0:
          primeFactors.append(divisor)
          while num % divisor == 0:
            num //= divisor
      # Handle the case that `num` contains a prime factor > 1000.
      if num > 1:
        primeFactors.append(num)
      return primeFactors

    for num in nums:
      for primeFactor in getPrimeFactors(num):
        rightPrimeFactors[primeFactor] += 1

    for i in range(len(nums) - 1):
      for primeFactor in getPrimeFactors(nums[i]):
        rightPrimeFactors[primeFactor] -= 1
        if rightPrimeFactors[primeFactor] == 0:
          # rightPrimeFactors[primeFactor] == 0, so no need to track
          # leftPrimeFactors[primeFactor].
          del rightPrimeFactors[primeFactor]
          del leftPrimeFactors[primeFactor]
        else:
          # Otherwise, need to track leftPrimeFactors[primeFactor].
          leftPrimeFactors[primeFactor] += 1
      if not leftPrimeFactors:
        return i

    return -1