#2584

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Split the Array to Make Coprime Products

Find the smallest index to split an array so that the products of two parts are coprime using array scanning and hash lookup.

array hash table math number theory

Problem Statement

Given a 0-indexed array nums of integers, find an index i where 0 <= i <= n - 2 such that the product of elements from nums[0] to nums[i] and the product of elements from nums[i+1] to nums[n-1] are coprime. Two numbers are coprime if their greatest common divisor (GCD) is 1.

Return the smallest valid index i that satisfies this condition, or -1 if no such index exists. A split is considered valid only if the two products share no common prime factor.

Examples

Example 1

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

Output: 2

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

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.length
1 <= n <= 104
1 <= nums[i] <= 106

Solution Approach

Prime Factor Tracking with Hash Map

Precompute prime factors for each element and maintain a hash map counting active primes. Scan the array from left to right, decrementing counts as primes move to the left product. When no active primes remain on the right, the current index is a valid split.

Efficient Array Scanning

Instead of computing full products, track prime factors' presence. Scanning the array once while updating the hash map avoids overflow and reduces unnecessary multiplications, ensuring fast detection of coprime splits.

Early Termination Optimization

Once a valid split is found where the left and right products share no primes, return the index immediately. This leverages the pattern that the first index without overlapping prime factors is always minimal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on prime factorization per element and array scanning, roughly O(n log(max(nums[i]))). Space complexity is dominated by the hash map storing prime counts, up to O(n log(max(nums[i]))) primes in worst case.

What Interviewers Usually Probe

Check if your solution avoids computing large products directly.
Ensure your prime factor tracking correctly identifies overlapping primes between subarrays.
Consider early stopping once the first valid split is detected.

Common Pitfalls or Variants

Common pitfalls

Attempting to multiply all elements causes integer overflow.
Forgetting to account for multiple occurrences of the same prime factor across the array.
Returning an index too late instead of the minimal valid index.

Follow-up variants

Find all valid split indices instead of just the smallest one.
Return the maximum index where a coprime split is possible.
Allow elements to be negative, adjusting GCD calculations accordingly.

FAQ

What is the main pattern used in Split the Array to Make Coprime Products?

The problem uses array scanning combined with hash lookup of prime factors to detect coprime product splits efficiently.

Why can't I just compute the product of subarrays directly?

Direct product computation can overflow and is inefficient; prime factor tracking avoids this and allows quick GCD checks.

How do I handle repeated prime factors in nums?

Count occurrences of each prime in a hash map and decrement as you move elements to the left subarray to track active primes.

What should be returned if no valid split exists?

Return -1 when no index produces left and right products that are coprime.

Is the first valid split always the minimal index?

Yes, scanning from left to right ensures the first index without overlapping prime factors is the smallest valid split.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        first = {}
        n = len(nums)
        last = list(range(n))
        for i, x in enumerate(nums):
            j = 2
            while j <= x // j:
                if x % j == 0:
                    if j in first:
                        last[first[j]] = i
                    else:
                        first[j] = i
                    while x % j == 0:
                        x //= j
                j += 1
            if x > 1:
                if x in first:
                    last[first[x]] = i
                else:
                    first[x] = i
        mx = last[0]
        for i, x in enumerate(last):
            if mx < i:
                return mx
            mx = max(mx, x)
        return -1

Continue Practicing

#2521 distinct prime factors of product of array #2748 number of beautiful pairs #3044 most frequent prime