LeetCode 2464 - Minimum Subarrays in a Valid Split

The problem asks us to split an array of integers nums into contiguous subarrays such that each subarray satisfies a validity condition: the greatest common divisor (GCD) of the first and last elements of the subarray must be strictly greater than 1.

leetcodemediumarraymathdynamic-programmingnumber-theory

LeetCode Problem 2464

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Number Theory

Solution

Problem Understanding

The problem asks us to split an array of integers nums into contiguous subarrays such that each subarray satisfies a validity condition: the greatest common divisor (GCD) of the first and last elements of the subarray must be strictly greater than 1. Each element in nums must belong to exactly one subarray. Our goal is to find the minimum number of subarrays that meet this criterion. If no valid split exists, we return -1.

The input nums is a list of integers where 1 <= nums.length <= 1000 and each element satisfies 1 <= nums[i] <= 10^5. These constraints indicate that a direct brute-force approach that tries every possible subarray split could be computationally expensive because the number of subarrays grows quadratically with the array length. Additionally, elements equal to 1 can never form a valid subarray with any other number because gcd(1, x) = 1, which is not greater than 1.

Important edge cases include arrays containing 1s, arrays where all elements are coprime with each other, arrays with all identical elements, and arrays of length 1.

Approaches

Brute Force

A brute-force approach would be to try all possible ways of splitting the array into contiguous subarrays and check if the first and last elements of each subarray satisfy the GCD condition. We would recursively try every possible partition and track the minimum number of subarrays. While this guarantees correctness, it is extremely inefficient because the number of partitions grows exponentially with the array length, making it infeasible for arrays of length up to 1000.

Optimal Approach

The key insight is that each valid subarray can be extended greedily from left to right as long as the GCD of the first element of the current subarray and the last element of the subarray segment considered is greater than 1. This allows us to scan the array in linear time while maintaining a dynamic programming array dp[i] representing the minimum number of valid subarrays ending at index i.

For each element nums[i], we check all possible starting positions j <= i for a subarray ending at i. If gcd(nums[j], nums[i]) > 1, we can form a valid subarray from j to i, and dp[i] is updated with dp[j-1] + 1 (or 1 if j = 0). After scanning, dp[n-1] contains the minimum number of valid subarrays for the entire array, or -1 if no valid split is possible.

This dynamic programming approach avoids checking all partitions and leverages the GCD condition to prune invalid subarrays efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries all partitions recursively; infeasible for n up to 1000
Optimal O(n^2 * log(max(nums))) O(n) DP approach with GCD checks; uses the property that valid subarrays depend on first and last element only

Algorithm Walkthrough

  1. Initialize a DP array dp of length n with inf, where dp[i] represents the minimum number of valid subarrays ending at index i.
  2. Iterate over each index i from 0 to n-1.
  3. For each i, iterate over possible starting indices j from 0 to i to form a subarray nums[j..i].
  4. Compute gcd(nums[j], nums[i]). If the GCD is greater than 1, the subarray is valid.
  5. Update dp[i] with dp[j-1] + 1 if j > 0, or 1 if j == 0.
  6. After processing all i, check dp[n-1]. If it is inf, return -1 because no valid split exists; otherwise, return dp[n-1].

Why it works: The algorithm works because dp[i] always stores the minimum number of subarrays required to split nums[0..i] validly. By considering all valid subarrays ending at i and updating dp[i] greedily, we ensure that each index is covered optimally. The invariant is that before processing index i, dp[0..i-1] already contains the minimum number of valid subarrays for their respective prefixes.

Python Solution

from math import gcd
from typing import List

class Solution:
    def validSubarraySplit(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:
                    if j == 0:
                        dp[i] = 1
                    else:
                        dp[i] = min(dp[i], dp[j-1] + 1)
        
        return dp[-1] if dp[-1] != float('inf') else -1

The Python implementation uses a nested loop where the outer loop iterates over the ending index i and the inner loop iterates over possible starting indices j. The gcd function is used to verify the validity of a subarray. The dp array is updated according to the rules explained above. Finally, the solution returns the minimum number of valid subarrays or -1 if none exist.

Go Solution

package main

import "math"

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func validSubarraySplit(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = math.MaxInt32
    }

    for i := 0; i < n; i++ {
        for j := 0; j <= i; j++ {
            if gcd(nums[j], nums[i]) > 1 {
                if j == 0 {
                    dp[i] = 1
                } else if dp[j-1] != math.MaxInt32 {
                    if dp[j-1]+1 < dp[i] {
                        dp[i] = dp[j-1] + 1
                    }
                }
            }
        }
    }

    if dp[n-1] == math.MaxInt32 {
        return -1
    }
    return dp[n-1]
}

The Go implementation mirrors the Python solution, with attention to slice initialization and handling math.MaxInt32 as a representation of infinity. The gcd function is implemented iteratively. Edge cases like empty slices are naturally handled because len(nums) is guaranteed to be at least 1.

Worked Examples

Example 1: nums = [2,6,3,4,3]

i j gcd(nums[j], nums[i]) dp[i] Explanation
0 0 2 1 Subarray [2] is valid
1 0 2 1 Subarray [2,6] is valid, dp[1] = 1
1 1 6 1 Subarray [6] is valid, dp[1] = 1
2 2 3 2 Subarray [3] valid, dp[2] = dp[1]+1 = 2
3 3 4 3 Subarray [4] valid, dp[3] = dp[2]+1 = 3
3 2 1 - Not valid
4 4 3 3 Subarray [3] valid, dp[4] = dp[3]+1 = 4
4 3 1 - Not valid
4 2 3 2 Subarray [3,4,3] valid, dp[4] = dp[1]+1 = 2

Result: dp[4] = 2

Example 2: nums = [3,5]

i j gcd(nums[j], nums[i]) dp[i]
0 0 3 1
1 1 5 2
1 0 1 -

Result: dp[1] = 2

Example 3: nums = [1,2,1]

All possible subarrays have gcd(first,last) <= 1, so dp[i] remains inf.

Result: -1

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 * log(max(nums))) Outer loop runs n times, inner loop runs up to n times, gcd calculation takes O(log(max(nums)))
Space O(n) The DP array of size n stores minimum subarrays for each prefix

The DP approach is feasible because n ≤ 1000, and even O(n^2) loops with efficient