3578. Count Partitions With Max-Min Difference at Most K

[mah-shamim]

Topics: Array, Dynamic Programming, Queue, Sliding Window, Prefix Sum, Monotonic Queue, Weekly Contest 453

You are given an integer array nums and an integer k. Your task is to partition nums into one or more non-empty contiguous segments such that in each segment, the difference between its maximum and minimum elements is at most k.

Return the total number of ways to partition nums under this condition.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

• Input: nums = [9,4,1,3,7], k = 4
• Output: 6
• Explanation: There are 6 valid partitions where the difference between the maximum and minimum elements in each segment is at most k = 4:
  • [[9], [4], [1], [3], [7]]
  • [[9], [4], [1], [3, 7]]
  • [[9], [4], [1, 3], [7]]
  • [[9], [4, 1], [3], [7]]
  • [[9], [4, 1], [3, 7]]
  • [[9], [4, 1, 3], [7]]

Example 2:

• Input: nums = [3,3,4], k = 0
• Output: 2
• Explanation: There are 2 valid partitions that satisfy the given conditions:
  • [[3], [3], [4]]
  • [[3, 3], [4]]

Constraints:

• 2 <= nums.length <= 5 * 10⁴
• 1 <= nums[i] <= 10⁹
• 0 <= k <= 10⁹

Hint:

1. Use dynamic programming.
2. Let dp[idx] be the count of ways to partition the array with the last partition ending at index idx.
3. Try using a sliding window; we can track the minimum and maximum in the window using deques.

[mah-shamim]

We need to count the number of ways to partition an array into contiguous segments where each segment's (max - min) ≤ k.
We need to count partitions where for each segment:

• max(segment) - min(segment) ≤ k

This is a dynamic programming problem where:

• dp[i] = number of valid partitions ending at index i
• The transition is: dp[i] = sum(dp[j-1]) for all j ≤ i where segment [j, i] is valid

Approach

We can solve this using:

1. Dynamic Programming to count ways
2. Sliding Window to find valid segments
3. Two Monotonic Queues to track min and max in current window
4. Prefix Sum to efficiently compute sums of dp values

Key Insight

For position i, we need to find the leftmost index left such that all segments ending at i starting from left to i are valid. Then:

• dp[i] = sum(dp[left-1] to dp[i-1]) (with base case dp[-1] = 1)

Let's implement this solution in PHP: 3578. Count Partitions With Max-Min Difference at Most K

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function countPartitions($nums, $k) {
    $MOD = 1000000007;
    $n = count($nums);

    // dp[i] = number of partitions ending at index i
    $dp = array_fill(0, $n, 0);
    // prefix sum of dp for O(1) range sum queries
    $prefixSum = array_fill(0, $n + 1, 0);
    $prefixSum[0] = 1; // base case: empty prefix has 1 way

    // Two deques: one for min, one for max (store indices)
    $minDeque = new SplDoublyLinkedList();
    $maxDeque = new SplDoublyLinkedList();

    $left = 0; // left boundary of current valid window

    for ($right = 0; $right < $n; $right++) {
        // Maintain min deque (increasing order)
        while (!$minDeque->isEmpty() && $nums[$minDeque->top()] >= $nums[$right]) {
            $minDeque->pop();
        }
        $minDeque->push($right);

        // Maintain max deque (decreasing order)
        while (!$maxDeque->isEmpty() && $nums[$maxDeque->top()] <= $nums[$right]) {
            $maxDeque->pop();
        }
        $maxDeque->push($right);

        // Shrink window from left until condition is satisfied
        while ($nums[$maxDeque->bottom()] - $nums[$minDeque->bottom()] > $k) {
            if ($minDeque->bottom() == $left) {
                $minDeque->shift();
            }
            if ($maxDeque->bottom() == $left) {
                $maxDeque->shift();
            }
            $left++;
        }

        // dp[right] = sum(dp[left-1] ... dp[right-1])
        // Using prefix sums: sum = prefixSum[right] - prefixSum[left-1]
        $sum = ($prefixSum[$right] - ($left > 0 ? $prefixSum[$left - 1] : 0) + $MOD) % $MOD;
        $dp[$right] = $sum;

        // Update prefix sum
        $prefixSum[$right + 1] = ($prefixSum[$right] + $dp[$right]) % $MOD;
    }

    return $dp[$n - 1] % $MOD;
}

// Test cases
echo countPartitions([9,4,1,3,7], 4) . "\n";    // Output: 6
echo countPartitions([3,3,4], 0) . "\n";        // Output: 2
?>

Explanation:

1. Monotonic Deques:

   • minDeque maintains indices with increasing values (minimum at front)
   • maxDeque maintains indices with decreasing values (maximum at front)

2. Sliding Window:

   • left is the start of the current valid window
   • For each right, we expand and maintain the deques
   • If max - min > k, we increment left and remove outdated indices from deques

3. Dynamic Programming:

   • dp[i] = sum of all dp[j] where j < i and segment [j+1, i] is valid
   • Using prefix sums allows O(1) computation of this sum

4. Base Case:

   • An empty array has 1 valid partition (doing nothing)
   • Represented as dp[-1] = 1 or prefixSum[0] = 1

Time Complexity: O(n)

• Each element is pushed and popped from the deques at most once
• We traverse the array once with the sliding window

Space Complexity: O(n)

• For dp array, prefix sum array, and the two deques

[basharul-siddike]

Thanks for solving the problem of "Count Partitions With Max-Min Difference at Most K"

[mah-shamim]

Thanks