Watch 10 video solutions for Split the Array to Make Coprime Products, a hard level problem involving Array, Hash Table, Math. This walkthrough by codingMohan has 2,570 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums of length n.
A split at an index i where 0 <= i <= n - 2 is called valid if the product of the first i + 1 elements and the product of the remaining elements are coprime.
nums = [2, 3, 3], then a split at the index i = 0 is valid because 2 and 9 are coprime, while a split at the index i = 1 is not valid because 6 and 3 are not coprime. A split at the index i = 2 is not valid because i == n - 1.Return the smallest index i at which the array can be split validly or -1 if there is no such split.
Two values val1 and val2 are coprime if gcd(val1, val2) == 1 where gcd(val1, val2) is the greatest common divisor of val1 and val2.
Example 1:
Input: nums = [4,7,8,15,3,5] Output: 2 Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i. The only valid split is at index 2.
Example 2:
Input: nums = [4,7,15,8,3,5] Output: -1 Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i. There is no valid split.
Constraints:
n == nums.length1 <= n <= 1041 <= nums[i] <= 106Problem Overview: You are given an integer array and must split it into two non-empty parts such that the product of the left subarray and the product of the right subarray are coprime. The task is to return the earliest split index where gcd(prefixProduct, suffixProduct) = 1.
The key observation is that two products are coprime if they share no common prime factors. Instead of multiplying large numbers (which quickly overflows), track the prime factors contributing to each side of the split.
Approach 1: Prefix and Suffix Product Approach (O(n log A) time, O(n) space)
This method explicitly models the idea of prefix and suffix products using prime factor tracking. First factorize each number and record which primes appear. Build prefix information by accumulating factors seen so far, and suffix information by tracking factors that appear later in the array. When scanning possible split points, check whether any prime factor exists on both sides. If the prefix and suffix share no common factors, the split is valid. Factorization costs O(log A) per element, giving overall O(n log A) time and O(n) extra space. This approach is straightforward and useful when you want a clear separation between prefix and suffix computations.
Approach 2: Cumulative Product with Single Pass (O(n log A) time, O(n) space)
A more optimized implementation tracks the last occurrence of every prime factor. Factorize each number and store the furthest index where each prime appears. Then scan the array once while maintaining the farthest boundary of any prime factor seen so far. If the current index equals that boundary, all prime factors from the left side end here, meaning none continue into the right side. That index forms a valid split because the two products cannot share factors. This technique uses a hash map for prime tracking and avoids maintaining full prefix/suffix structures.
This problem heavily relies on concepts from number theory, efficient prime factorization on arrays, and fast lookups using a hash table. Managing ranges and boundaries across an array is the core implementation detail.
Recommended for interviews: The single-pass cumulative approach. Interviewers expect you to recognize that multiplying values is unnecessary and that prime factor overlap determines coprimality. Showing the prefix/suffix reasoning demonstrates understanding, but the boundary-tracking solution shows stronger algorithmic insight and cleaner implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Product Approach | O(n log A) | O(n) | When you want explicit prefix and suffix factor tracking for clarity |
| Cumulative Product with Single Pass | O(n log A) | O(n) | General optimal solution using last occurrence of prime factors |