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

Source: Dev.to

Problem

You are given an integer array nums and an integer k. 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 large, return it modulo 10⁹ + 7.

Example

Example 1

Input:  nums = [9,4,1,3,7], k = 4
Output: 6

Valid partitions (max‑min ≤ 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

Valid partitions:

• [[3], [3], [4]]
• [[3,3], [4]]

Constraints

• 2 ≤ nums.length ≤ 5·10⁴
• 1 ≤ nums[i] ≤ 10⁹
• 0 ≤ k ≤ 10⁹

Hint

• Use dynamic programming.
• Let dp[i] be the number of ways to partition the array with the last segment ending at index i.
• A sliding window together with two monotonic deques can maintain the minimum and maximum of the current window.

Solution Overview

We need to count partitions where every segment satisfies max(segment) - min(segment) ≤ k.

Dynamic Programming

Define dp[i] as the number of valid partitions of the prefix nums[0…i] (the last segment ends at i).
For a segment [j, i] to be valid, the window [j, i] must satisfy the max‑min condition. Then

[ dp[i] = \sum_{j=0}^{i} dp[j-1] \quad\text{for all } j \text{ such that } [j,i] \text{ is valid} ]

with the base case dp[-1] = 1 (empty prefix).
Using a prefix‑sum array pref, the sum above becomes dp[i] = pref[i] - pref[left-2], where left is the leftmost index that can start a valid segment ending at i.

Sliding Window with Monotonic Queues

Maintain a window [left, right] where right iterates from 0 to n‑1.
Two deques store indices:

• minDeque: increasing values → front holds the minimum.
• maxDeque: decreasing values → front holds the maximum.

When adding right, pop from the back of each deque while the new element breaks monotonicity, then push right.

If maxDeque.front() - minDeque.front() > k, shrink the window by incrementing left and removing indices that fall out of the window from both deques.

After adjusting, left is the smallest start index for a valid segment ending at right.

Computing dp with Prefix Sums

Maintain pref[i] = (pref[i‑1] + dp[i]) mod M, where M = 1_000_000_007.

For each right = i:

dp[i] = pref[i-1] - (left > 0 ? pref[left-2] : 0)
dp[i] = (dp[i] + M) % M   // ensure non‑negative
pref[i] = (pref[i-1] + dp[i]) % M

The answer is dp[n‑1].

Complexity

• Time: O(n) – each index is pushed/popped from the deques at most once.
• Space: O(n) – for dp, pref, and the two deques.

Reference Implementation (PHP)

setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
    $maxDeque->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);

    $left = 0;

    for ($right = 0; $right isEmpty() && $nums[$minDeque->top()] >= $nums[$right]) {
            $minDeque->pop();
        }
        $minDeque->push($right);

        // maintain monotonic max deque
        while (!$maxDeque->isEmpty() && $nums[$maxDeque->top()] pop();
        }
        $maxDeque->push($right);

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

        // compute dp[right]
        $total = $right > 0 ? $pref[$right - 1] : 0;
        $sub   = ($left > 0) ? $pref[$left - 2] : 0;
        $dp[$right] = ($total - $sub + $mod) % $mod;

        // update prefix sum
        $pref[$right] = ($total + $dp[$right]) % $mod;
    }

    return $dp[$n - 1];
}

// Test cases
echo countPartitions([9, 4, 1, 3, 7], 4) . PHP_EOL; // 6
echo countPartitions([3, 3, 4], 0) . PHP_EOL;       // 2
?>