How hard is LeetCode 2464. Minimum Subarrays in a Valid Split?

LeetCode 2464. Minimum Subarrays in a Valid Split is rated Medium on LeetCode.

What is the time complexity of LeetCode 2464. Minimum Subarrays in a Valid Split?

The Python solution on this page runs in O(n^2).

What is the space complexity of LeetCode 2464. Minimum Subarrays in a Valid Split?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2464. Minimum Subarrays in a Valid Split cover?

LeetCode 2464. Minimum Subarrays in a Valid Split is tagged Array, Math, Dynamic Programming and Number Theory on LeetCode.

Is LeetCode 2464. Minimum Subarrays in a Valid Split a premium problem?

Yes. LeetCode 2464. Minimum Subarrays in a Valid Split is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Minimum Subarrays in a Valid Split — LeetCode 2464 Python Solution

MediumLeetCode PremiumArrayMathDynamic ProgrammingNumber Theory

Problem: #2464
Pattern: Dynamic Programming
Reading time: 3 min
Source: leetcode.com

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

Example

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].

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n^2)
Space	O(n) auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2464. Minimum Subarrays in a Valid Split is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2464. Minimum Subarrays in a Valid Split?: LeetCode 2464. Minimum Subarrays in a Valid Split is rated Medium on LeetCode.
What is the time complexity of LeetCode 2464. Minimum Subarrays in a Valid Split?: The Python solution on this page runs in O(n^2).
What is the space complexity of LeetCode 2464. Minimum Subarrays in a Valid Split?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2464. Minimum Subarrays in a Valid Split cover?: LeetCode 2464. Minimum Subarrays in a Valid Split is tagged Array, Math, Dynamic Programming and Number Theory on LeetCode.
Is LeetCode 2464. Minimum Subarrays in a Valid Split a premium problem?: Yes. LeetCode 2464. Minimum Subarrays in a Valid Split is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.