Split the array to make coprime products

Array Hash Table Math Number Theory

28.7% acceptance

Feb 25, 2026

321

112

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. For example, if 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_valid_split(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // For each prime p, track first and last occurrence index
    let mut first: std::collections::HashMap<i32, usize> = std::collections::HashMap::new();
    let mut last: std::collections::HashMap<i32, usize> = std::collections::HashMap::new();

    let factorize = |mut x: i32, idx: usize,
              first: &mut std::collections::HashMap<i32, usize>,
              last: &mut std::collections::HashMap<i32, usize>| {
      let mut d = 2;
      while d * d <= x {
        if x % d == 0 {
          first.entry(d).or_insert(idx);
          last.insert(d, idx);
          while x % d == 0 { x /= d; }
        }
        d += 1;
      }
      if x > 1 {
        first.entry(x).or_insert(idx);
        last.insert(x, idx);
      }
    };

    for (i, &num) in nums.iter().enumerate() {
      factorize(num, i, &mut first, &mut last);
    }

    // active_count = # primes where first[p] <= i < last[p]
    let mut active = 0i32;
    let mut prime_first_at: Vec<Vec<i32>> = vec![vec![]; n];
    let mut prime_last_at: Vec<Vec<i32>> = vec![vec![]; n];
    for (&p, &fi) in &first {
      prime_first_at[fi].push(p);
    }
    for (&p, &li) in &last {
      prime_last_at[li].push(p);
    }

    for i in 0..n - 1 {
      active += prime_first_at[i].len() as i32;
      active -= prime_last_at[i].len() as i32;
      if active == 0 { return i as i32; }
    }
    -1
  }
}