Minimum Partition Count with Length and Range Constraints

hard

Dynamic Programming Monotonic Stack Sliding Window

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.

Example 1

Input

[
  "[1, 3, 6, 2, 8, 5, 9]",
  "2",
  "5"
]

Output

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.

Example 2

Input

[
  "[10, 1, 10, 1]",
  "2",
  "2"
]

Output

-1

Explanation. Any contiguous subarray of length >= 2 contains both 10 and 1, yielding a max-min difference of 9 > 2. No valid partition exists.

Example 3

Input

[
  "[5, 5, 5, 5, 5]",
  "1",
  "0"
]

Output

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.

Example 4

Input

[
  "[1, 2, 10, 11, 12]",
  "2",
  "2"
]

Output

Explanation. The optimal partition is [1, 2] (max-min = 1 <= 2) and [10, 11, 12] (max-min = 2 <= 2).

Example 5

Input

[
  "[4, 2, 3, 8, 9, 7, 12, 10, 11]",
  "2",
  "3"
]

Output

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?

Constraints:

1 <= nums.length <= 10^5 1 <= min_len <= nums.length 0 <= max_diff <= 10^9 1 <= nums[i] <= 10^9

Views: 1