LeetCode 2584 - Split the Array to Make Coprime Products

The problem is asking us to find a valid split point in an array nums where the product of elements to the left of the split and the product of elements to the right are coprime. Formally, if we split at index i, the left product is nums[0] nums[1] ...

leetcodehardarrayhash-tablemathnumber-theory

LeetCode Problem 2584

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Number Theory

Solution

Problem Understanding

The problem is asking us to find a valid split point in an array nums where the product of elements to the left of the split and the product of elements to the right are coprime. Formally, if we split at index i, the left product is nums[0] * nums[1] * ... * nums[i] and the right product is nums[i+1] * ... * nums[n-1]. The split is valid if gcd(left_product, right_product) == 1.

The input is a 0-indexed array of integers where 1 <= nums[i] <= 10^6 and the array length n can go up to 10^4. The output is the smallest valid split index, or -1 if no valid split exists.

Naive implementations might fail due to integer overflow or excessive computation since directly calculating products can grow extremely large. Also, checking the GCD repeatedly on full products for every split is inefficient. Edge cases include arrays where all elements are prime, arrays with repeated factors, or arrays where no valid split exists.

Approaches

Brute-Force Approach: The naive method calculates the product of the left and right subarrays for every possible split index i and checks if their GCD is 1. This guarantees correctness but is infeasible for the given constraints, as products can exceed 64-bit integers, and calculating them repeatedly results in O(n²) complexity.

Optimal Approach: The key insight is that two numbers are coprime if they share no prime factors. Instead of calculating full products, we track the prime factors of each element. By maintaining a map of the last occurrence of each prime factor in the array, we know the earliest index where any prime factor still exists on the right. The valid split occurs before any prime factor's last occurrence.

This reduces the problem to factoring numbers and tracking prime ranges efficiently using a hash map, avoiding large integer multiplications.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² log M) O(1) Calculates products and GCDs directly, where M is the maximum product value
Optimal O(n log M) O(n) Factorizes numbers and tracks last occurrence of each prime factor

Algorithm Walkthrough

  1. Prime Factorization Map: For each element in nums, compute its prime factors. Use trial division up to √num for efficiency.
  2. Track Last Occurrences: Maintain a dictionary last_occurrence mapping each prime factor to the last index it appears in nums.
  3. Initialize Split Tracking: Set max_last_index = 0 which will track the rightmost index where a prime factor has its last occurrence affecting the current split.
  4. Iterate Array: For each index i:
  • For each prime factor of nums[i], update max_last_index to max(max_last_index, last_occurrence[prime]).
  • If i == max_last_index, all prime factors from 0 to i are no longer in the remaining array, making the left and right products coprime. Return i.
  1. No Split Found: If the iteration completes without finding such an index, return -1.

Why it works: This works because any prime factor appearing in both left and right subarrays prevents coprimality. By tracking the last occurrence of each prime, we ensure all remaining elements in the right subarray have no shared primes with the left subarray when i == max_last_index.

Python Solution

from typing import List
import math

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        def prime_factors(x):
            factors = set()
            d = 2
            while d * d <= x:
                while x % d == 0:
                    factors.add(d)
                    x //= d
                d += 1
            if x > 1:
                factors.add(x)
            return factors
        
        last_occurrence = {}
        n = len(nums)
        
        # Compute last occurrence of each prime factor
        for i, num in enumerate(nums):
            for p in prime_factors(num):
                last_occurrence[p] = i
        
        max_last_index = 0
        for i, num in enumerate(nums):
            for p in prime_factors(num):
                max_last_index = max(max_last_index, last_occurrence[p])
            if i == max_last_index:
                return i
        return -1

The Python code computes prime factors for each number, maps the last index of each prime factor, and iterates to determine the earliest valid split. This avoids computing large products and ensures correctness for large numbers.

Go Solution

func findValidSplit(nums []int) int {
    n := len(nums)
    lastOccurrence := make(map[int]int)
    
    // Helper function to get prime factors
    primeFactors := func(x int) map[int]struct{} {
        factors := make(map[int]struct{})
        for d := 2; d*d <= x; d++ {
            for x%d == 0 {
                factors[d] = struct{}{}
                x /= d
            }
        }
        if x > 1 {
            factors[x] = struct{}{}
        }
        return factors
    }
    
    // Compute last occurrence of each prime factor
    for i, num := range nums {
        for p := range primeFactors(num) {
            lastOccurrence[p] = i
        }
    }
    
    maxLastIndex := 0
    for i, num := range nums {
        for p := range primeFactors(num) {
            if lastOccurrence[p] > maxLastIndex {
                maxLastIndex = lastOccurrence[p]
            }
        }
        if i == maxLastIndex {
            return i
        }
    }
    return -1
}

In Go, we use maps and structs to represent prime factors. The approach is analogous to Python, ensuring no integer overflow and correct handling of slices.

Worked Examples

Example 1: nums = [4,7,8,15,3,5]

i num Prime factors max_last_index Valid split?
0 4 {2} 4 No
1 7 {7} 4 No
2 8 {2} 4 No
3 15 {3,5} 4 No
4 3 {3} 4 Yes → return 2

Example 2: nums = [4,7,15,8,3,5]

No index satisfies the condition → return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n log M) Factorizing each element takes O(√M), which is approximately O(log M) for practical purposes; iterating n elements
Space O(n) Store last occurrences of prime factors, at most one entry per factor per number

Factorization dominates time, but is efficient for nums[i] <= 10^6. Space is linear in the number of unique primes across the array.

Test Cases

# Provided examples
assert Solution().findValidSplit([4,7,8,15,3,5]) == 2  # valid split exists
assert Solution().findValidSplit([4,7,15,8,3,5]) == -1 # no valid split

# Edge cases
assert Solution().findValidSplit([2,3,5,7]) == 0  # first split is valid, all primes
assert Solution().findValidSplit([6,10,15]) == -1 # all share prime factors
assert Solution().findValidSplit([1,1,1]) == 0    # split at first index
assert Solution().findValidSplit([2]) == -1       # cannot split single element
assert Solution().findValidSplit([2,4,8,16,32]) == -1 # powers of two, no coprime split
Test Why
[4,7,8,15,3,5] Basic valid split test
[4,7,15,8,3,5] No valid split exists
[2,3,5,7] All primes, split at first index
[6,10,15] Shared prime factors prevent splits
[1,1,1] Edge case with ones
[2] Single element, cannot split
[2,4,8,16,32] Repeated prime factors, no coprime split

Edge Cases

  1. Single-element array: nums = [x] cannot be split, so the function returns -1. Handling this explicitly is unnecessary as the loop never finds a valid split.
  2. All elements are powers of a single prime: For example, [2,4,8,16]. Each split shares the prime factor 2, so no valid split exists. The algorithm correctly returns -1 since max_last_index never equals i until the end.
  3. **Array of ones