MediumNo. 2464LeetCode Premium
Minimum Subarrays in a Valid Split — LeetCode 2464 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Math, Dynamic Programming, Number Theory
- 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
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 -1Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1735 | Count Ways to Make Array With Product | Hard |
| 1799 | Maximize Score After N Operations | Hard |
| 0313 | Super Ugly Number | Medium |
| 0368 | Largest Divisible Subset | Medium |
| 0396 | Rotate Function | Medium |
| 0486 | Predict the Winner | Medium |
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(n2).
- 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.