Minimum Subarrays in a Valid Split
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array nums.
Splitting of an integer array nums into subarrays is valid if:
- the greatest common divisor of the first and last elements of each subarray is greater than
1, and - each element of
numsbelongs to exactly one subarray.
Return theminimum number of subarrays in a valid subarray splitting of nums. If a valid subarray splitting is not possible, return -1.
Note that:
- The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
- A subarray is a contiguous non-empty part of an array.
Examples
Example 1:
Input: nums = [2,6,3,4,3]
Output: 2
Explanation: We can create a valid split in the following way: [2,6] | [3,4,3].
- The starting element of the 1st subarray is 2 and the ending is 6. Their greatest common divisor is 2, which is greater than 1.
- The starting element of the 2nd subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.
Example 2:
Input: nums = [3,5]
Output: 2
Explanation: We can create a valid split in the following way: [3] | [5].
- The starting element of the 1st subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
- The starting element of the 2nd subarray is 5 and the ending is 5. Their greatest common divisor is 5, which is greater than 1.
It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.
Example 3:
Input: nums = [1,2,1]
Output: -1
Explanation: It is impossible to create valid split.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 10^5
Solution
Method 1 – Dynamic Programming (Greedy Split)
Intuition
We want to split the array into the minimum number of contiguous subarrays such that the GCD of the first and last element of each subarray is greater than 1. We can use DP: for each position, try to extend the current subarray as far as possible, and split only when necessary.
Approach
Let dp[i] be the minimum number of subarrays for nums[0..i]. For each j < i, if gcd(nums[j], nums[i]) > 1, we can split at j. We initialize dp[0] = 1, and for each i, check all possible splits.
Code
C++
#include <numeric>
class Solution {
public:
int minimumSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1e9);
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (gcd(nums[j], nums[i]) > 1) {
dp[i] = min(dp[i], (j ? dp[j-1] : 0) + 1);
}
}
}
return dp[n-1] >= 1e9 ? -1 : dp[n-1];
}
};
Go
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func minimumSubarrays(nums []int) int {
n := len(nums)
dp := make([]int, n)
for i := range dp { dp[i] = 1e9 }
for i := 0; i < n; i++ {
for j := 0; j <= i; j++ {
if gcd(nums[j], nums[i]) > 1 {
prev := 0
if j > 0 { prev = dp[j-1] }
if prev+1 < dp[i] { dp[i] = prev+1 }
}
}
}
if dp[n-1] >= 1e9 { return -1 }
return dp[n-1]
}
Java
class Solution {
private int gcd(int a, int b) {
while (b != 0) {
int t = b; b = a % b; a = t;
}
return a;
}
public int minimumSubarrays(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (gcd(nums[j], nums[i]) > 1) {
int prev = j > 0 ? dp[j-1] : 0;
dp[i] = Math.min(dp[i], prev+1);
}
}
}
return dp[n-1] == Integer.MAX_VALUE ? -1 : dp[n-1];
}
}
Kotlin
class Solution {
private fun gcd(a: Int, b: Int): Int {
var x = a; var y = b
while (y != 0) { val t = y; y = x % y; x = t }
return x
}
fun minimumSubarrays(nums: IntArray): Int {
val n = nums.size
val dp = IntArray(n) { Int.MAX_VALUE }
for (i in 0 until n) {
for (j in 0..i) {
if (gcd(nums[j], nums[i]) > 1) {
val prev = if (j > 0) dp[j-1] else 0
dp[i] = minOf(dp[i], prev+1)
}
}
}
return if (dp[n-1] == Int.MAX_VALUE) -1 else dp[n-1]
}
}
Python
from math import gcd
class Solution:
def minimumSubarrays(self, nums: list[int]) -> int:
n = len(nums)
dp = [float('inf')] * n
for i in range(n):
for j in range(i+1):
if gcd(nums[j], nums[i]) > 1:
prev = dp[j-1] if j > 0 else 0
dp[i] = min(dp[i], prev+1)
return -1 if dp[-1] == float('inf') else dp[-1]
Rust
impl Solution {
pub fn minimum_subarrays(nums: Vec<i32>) -> i32 {
fn gcd(mut a: i32, mut b: i32) -> i32 {
while b != 0 { let t = b; b = a % b; a = t; } a
}
let n = nums.len();
let mut dp = vec![i32::MAX; n];
for i in 0..n {
for j in 0..=i {
if gcd(nums[j], nums[i]) > 1 {
let prev = if j > 0 { dp[j-1] } else { 0 };
dp[i] = dp[i].min(prev+1);
}
}
}
if dp[n-1] == i32::MAX { -1 } else { dp[n-1] }
}
}
TypeScript
function gcd(a: number, b: number): number {
while (b !== 0) { let t = b; b = a % b; a = t; } return a;
}
class Solution {
minimumSubarrays(nums: number[]): number {
const n = nums.length;
const dp = Array(n).fill(Infinity);
for (let i = 0; i < n; i++) {
for (let j = 0; j <= i; j++) {
if (gcd(nums[j], nums[i]) > 1) {
const prev = j > 0 ? dp[j-1] : 0;
dp[i] = Math.min(dp[i], prev+1);
}
}
}
return dp[n-1] === Infinity ? -1 : dp[n-1];
}
}
Complexity
- ⏰ Time complexity:
O(n^2)— For each end, try all starts. - 🧺 Space complexity:
O(n)— For DP array.