2464. Minimum Subarrays in a Valid Split 🔒

DifficultyMedium

Description

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 nums belongs to exactly one subarray.

Return the minimum 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.

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 1^st subarray is 2 and the ending is 6. Their greatest common divisor is 2, which is greater than 1.
- The starting element of the 2^nd 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 1^st subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
- The starting element of the 2^nd 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 <= 1000
1 <= nums[i] <= 10⁵

Solutions

Solution 1: Memoization Search

Thinking

A piece is valid iff the GCD of its endpoints exceeds \(1\), and we want the fewest pieces. From \(i\), try every right end \(j\) and take \(1+\textit{dfs}(j+1)\) when the GCD allows. Memoized \(O(n^2)\) GCDs; return \(-1\) if unbounded.

We design a function \(\textit{dfs}(i)\) to represent the minimum number of partitions starting from index \(i\). For index \(i\), we can enumerate all partition points \(j\), i.e., \(i \leq j < n\), where \(n\) is the length of the array. For each partition point \(j\), we need to determine whether the greatest common divisor of \(\textit{nums}[i]\) and \(\textit{nums}[j]\) is greater than \(1\). If it is greater than \(1\), we can partition, and the number of partitions is \(1 + \textit{dfs}(j + 1)\); otherwise, the number of partitions is \(+\infty\). Finally, we take the minimum of all partition numbers.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

Python3JavaC++Go

class Solution:
    def validSubarraySplit(self, nums: List[int]) -> int:
        @cache
        def dfs(i):
            if i >= n:
                return 0
            ans = inf
            for j in range(i, n):
                if gcd(nums[i], nums[j]) > 1:
                    ans = min(ans, 1 + dfs(j + 1))
            return ans

        n = len(nums)
        ans = dfs(0)
        dfs.cache_clear()
        return ans if ans < inf else -1

class Solution {
    private int n;
    private int[] f;
    private int[] nums;
    private int inf = 0x3f3f3f3f;

    public int validSubarraySplit(int[] nums) {
        n = nums.length;
        f = new int[n];
        this.nums = nums;
        int ans = dfs(0);
        return ans < inf ? ans : -1;
    }

    private int dfs(int i) {
        if (i >= n) {
            return 0;
        }
        if (f[i] > 0) {
            return f[i];
        }
        int ans = inf;
        for (int j = i; j < n; ++j) {
            if (gcd(nums[i], nums[j]) > 1) {
                ans = Math.min(ans, 1 + dfs(j + 1));
            }
        }
        f[i] = ans;
        return ans;
    }

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

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    int validSubarraySplit(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        function<int(int)> dfs = [&](int i) -> int {
            if (i >= n) return 0;
            if (f[i]) return f[i];
            int ans = inf;
            for (int j = i; j < n; ++j) {
                if (__gcd(nums[i], nums[j]) > 1) {
                    ans = min(ans, 1 + dfs(j + 1));
                }
            }
            f[i] = ans;
            return ans;
        };
        int ans = dfs(0);
        return ans < inf ? ans : -1;
    }
};

func validSubarraySplit(nums []int) int {
    n := len(nums)
    f := make([]int, n)
    var dfs func(int) int
    const inf int = 0x3f3f3f3f
    dfs = func(i int) int {
        if i >= n {
            return 0
        }
        if f[i] > 0 {
            return f[i]
        }
        ans := inf
        for j := i; j < n; j++ {
            if gcd(nums[i], nums[j]) > 1 {
                ans = min(ans, 1+dfs(j+1))
            }
        }
        f[i] = ans
        return ans
    }
    ans := dfs(0)
    if ans < inf {
        return ans
    }
    return -1
}

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

Solution 2: Dynamic Programming

Thinking

Enumerating every split is exponential. The array length reaches \(1000\), and the next piece always starts strictly to the right, so a search from the left has depth \(n\). A piece is valid exactly when the GCD of its endpoints is greater than \(1\), so the answer from index \(i\) depends only on later answers. Let \(f[i]\) be the fewest pieces starting at \(i\), with \(f[n]=0\), and scan right endpoints from the end of the array, updating with \(1+f[j+1]\) whenever \(\gcd(\textit{nums}[i], \textit{nums}[j])>1\).

Let \(f[i]\) be the minimum number of pieces starting at index \(i\), with \(f[n]=0\). For \(i\) from \(n-1\) down to \(0\), enumerate the right endpoint \(j\) (\(i \leq j < n\)). If \(\gcd(\textit{nums}[i], \textit{nums}[j]) > 1\), the range \([i, j]\) is one valid piece, and \(f[i]\) is updated with \(1 + f[j + 1]\). If \(f[0]\) is still infinite, no valid split exists and the answer is \(-1\); otherwise the answer is \(f[0]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

Python3JavaC++Go

class Solution:
    def validSubarraySplit(self, nums: List[int]) -> int:
        n = len(nums)
        f = [inf] * (n + 1)
        f[n] = 0
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if gcd(nums[i], nums[j]) > 1:
                    f[i] = min(f[i], 1 + f[j + 1])
        return f[0] if f[0] < inf else -1

class Solution {
    public int validSubarraySplit(int[] nums) {
        int n = nums.length;
        int inf = 0x3f3f3f3f;
        int[] f = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            f[i] = inf;
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (gcd(nums[i], nums[j]) > 1) {
                    f[i] = Math.min(f[i], 1 + f[j + 1]);
                }
            }
        }
        return f[0] < inf ? f[0] : -1;
    }

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

class Solution {
public:
    int validSubarraySplit(vector<int>& nums) {
        int n = nums.size();
        const int inf = 0x3f3f3f3f;
        vector<int> f(n + 1, inf);
        f[n] = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (__gcd(nums[i], nums[j]) > 1) {
                    f[i] = min(f[i], 1 + f[j + 1]);
                }
            }
        }
        return f[0] < inf ? f[0] : -1;
    }
};

func validSubarraySplit(nums []int) int {
    n := len(nums)
    const inf int = 0x3f3f3f3f
    f := make([]int, n+1)
    for i := 0; i < n; i++ {
        f[i] = inf
    }
    for i := n - 1; i >= 0; i-- {
        for j := i; j < n; j++ {
            if gcd(nums[i], nums[j]) > 1 {
                f[i] = min(f[i], 1+f[j+1])
            }
        }
    }
    if f[0] < inf {
        return f[0]
    }
    return -1
}

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

2464. Minimum Subarrays in a Valid Split 🔒

Description

Solutions

Solution 1: Memoization Search

Solution 2: Dynamic Programming

Comments