Skip to content

2464. Minimum Subarrays in a Valid Split 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int validSubarraySplit(vector<int>& nums) {
    constexpr int kMax = INT_MAX / 2;
    // dp[i] := the minimum number of subarrays to validly split nums[0..i]
    vector<int> dp(nums.size(), kMax);

    for (int i = 0; i < nums.size(); ++i)
      for (int j = 0; j <= i; ++j)
        if (__gcd(nums[j], nums[i]) > 1)
          dp[i] = min(dp[i], j == 0 ? 1 : dp[j - 1] + 1);

    return dp.back() == kMax ? -1 : dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int validSubarraySplit(int[] nums) {
    final int kMax = Integer.MAX_VALUE / 2;
    final int n = nums.length;
    // dp[i] := the minimum number of subarrays to validly split nums[0..i]
    int[] dp = new int[n];
    Arrays.fill(dp, kMax);

    for (int i = 0; i < n; ++i)
      for (int j = 0; j <= i; ++j)
        if (gcd(nums[j], nums[i]) > 1)
          dp[i] = Math.min(dp[i], j == 0 ? 1 : dp[j - 1] + 1);

    return dp[n - 1] == kMax ? -1 : dp[n - 1];
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def validSubarraySplit(self, nums: list[int]) -> int:
    # dp[i] := the minimum number of subarrays to validly split nums[0..i]
    dp = [math.inf] * len(nums)

    for i, num in enumerate(nums):
      for j in range(i + 1):
        if math.gcd(nums[j], num) > 1:
          dp[i] = min(dp[i], 1 if j == 0 else dp[j - 1] + 1)

    return -1 if dp[-1] == math.inf else dp[-1]