Minimum Partition Count with Length and Range Constraints
Given an array of integers nums, an integer min_len, and an integer max_diff, partition the array into contiguous non-empty subarrays such that:
- Every subarray has a length of at least
min_len. - For every subarray, the difference between its maximum element and its minimum element does not exceed
max_diff(i.e., $\max(subarray) - \min(subarray) \le max_diff$).
Return the minimum number of subarrays needed to partition the entire array subject to these conditions. If no valid partition exists, return -1.
[ "[1, 3, 6, 2, 8, 5, 9]", "2", "5" ]
Explanation. The optimal partition is [1, 3, 6, 2] (length 4 >= 2, max-min = 6-1 = 5 <= 5) and [8, 5, 9] (length 3 >= 2, max-min = 9-5 = 4 <= 5). Total 2 subarrays.
[ "[10, 1, 10, 1]", "2", "2" ]
Explanation. Any contiguous subarray of length >= 2 contains both 10 and 1, yielding a max-min difference of 9 > 2. No valid partition exists.
[ "[5, 5, 5, 5, 5]", "1", "0" ]
Explanation. The entire array can be taken as 1 single subarray [5, 5, 5, 5, 5] with length 5 >= 1 and max-min difference 0 <= 0.
[ "[1, 2, 10, 11, 12]", "2", "2" ]
Explanation. The optimal partition is [1, 2] (max-min = 1 <= 2) and [10, 11, 12] (max-min = 2 <= 2).
[ "[4, 2, 3, 8, 9, 7, 12, 10, 11]", "2", "3" ]
Explanation. The optimal partition consists of 3 subarrays: [4, 2, 3] (max-min = 2 <= 3), [8, 9, 7] (max-min = 2 <= 3), and [12, 10, 11] (max-min = 2 <= 3).
Follow-up: Can you solve this problem in O(N) time complexity using dynamic programming optimized with monotonic deques?
1 <= nums.length <= 10^5 1 <= min_len <= nums.length 0 <= max_diff <= 10^9 1 <= nums[i] <= 10^9
- Views
- 7