2647. Split the Array to Make Coprime Products
My accepted Python solution to LeetCode problem 2647, Split the Array to Make Coprime Products, running in 4508ms.
- Difficulty: Hard
- Python
- Runtime 4508ms
- Memory 19MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 4508ms, memory 19MB, accepted 2025-12-31.
class Solution:
def findValidSplit(self, nums: List[int]) -> int:
n = len(nums)
# Get prime factors and their last occurrence
def prime_factors(x):
factors = []
d = 2
while d * d <= x:
if x % d == 0:
factors.append(d)
while x % d == 0:
x //= d
d += 1
if x > 1:
factors.append(x)
return factors
# For each prime, track its last occurrence
last_occurrence = {}
for i in range(n):
for p in prime_factors(nums[i]):
last_occurrence[p] = i
# Find the first valid split point
# A split at i is valid if no prime in prefix appears in suffix
max_last = 0
for i in range(n - 1):
for p in prime_factors(nums[i]):
max_last = max(max_last, last_occurrence[p])
# If all primes in prefix end at or before i, we can split
if max_last <= i:
return i
return -1