LeetCode Challenge Day 82 — 3578. Count Partitions With Max-Min Difference at Most K

Hey folks 👋

This is Day 82 of my LeetCode streak 🚀
Today’s problem is 3578. Count Partitions With Max-Min Difference at Most K — a very practical problem that combines multiple classic techniques.

📌 Problem Statement

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:

max(segment) - min(segment) ≤ k

Return the total number of valid ways to partition the array.
Since the answer can be large, return it modulo 10⁹ + 7.

💡 Intuition

Brute-forcing all possible partitions is exponential and clearly impossible for large inputs.

Key observation:

For a fixed right endpoint i, once we find the leftmost valid index L such that the subarray [L..i] satisfies:

max - min ≤ k

then every subarray [l..i] where l ≥ L is also valid.

So the problem reduces to:

• Efficiently maintaining a valid sliding window
• Counting how many valid partition endings are possible at each index

🔑 Approach

We combine Dynamic Programming, Sliding Window, and Monotonic Deques:

Dynamic Programming

• Let dp[i] = number of valid ways to partition nums[0..i-1].

Sliding Window

• Maintain a window [left..r] such that max - min ≤ k.

Monotonic Queues

• A decreasing deque to track the maximum in the window
• An increasing deque to track the minimum in the window

Prefix Sum Optimization

For each index r:

• Let L be the smallest valid left
• All partitions ending at r can start from any index in [L, r]
• Hence:

dp[r + 1] = dp[L] + dp[L + 1] + ... + dp[r]

We use a prefix sum array to compute this in O(1) time.

⏱️ Complexity Analysis

• Time Complexity: O(n)
  Each element is added and removed from the deques at most once.

• Space Complexity: O(n)
  For DP, prefix sums, and deques.

🧑‍💻 Code (JavaScript)

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var countPartitions = function(nums, k) {
  const MOD = 1_000_000_007;
  const n = nums.length;

  const dp = new Array(n + 1).fill(0);
  const pref = new Array(n + 2).fill(0);

  dp[0] = 1;
  pref[1] = 1;

  let left = 0;
  const maxQ = [];
  const minQ = [];
  let maxF = 0, minF = 0;

  for (let r = 0; r < n; r++) {
      while (maxQ.length > maxF && nums[maxQ[maxQ.length - 1]] <= nums[r]) {
          maxQ.pop();
      }
      maxQ.push(r);

      while (minQ.length > minF && nums[minQ[minQ.length - 1]] >= nums[r]) {
          minQ.pop();
      }
      minQ.push(r);

      while (true) {
          while (maxF < maxQ.length && maxQ[maxF] < left) maxF++;
          while (minF < minQ.length && minQ[minF] < left) minF++;

          if (nums[maxQ[maxF]] - nums[minQ[minF]] <= k) break;
          left++;
      }

      let ways = (pref[r + 1] - pref[left]) % MOD;
      if (ways < 0) ways += MOD;

      dp[r + 1] = ways;
      pref[r + 2] = (pref[r + 1] + dp[r + 1]) % MOD;
  }

  return dp[n];
};

🧩 Example Walkthrough

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

Valid partitions = 6

The sliding window ensures we only consider segments that obey the max - min ≤ k rule, and DP counts all valid combinations efficiently.

🎯 Reflection

This problem is a great example of how:

• Sliding windows can prune invalid ranges

• Monotonic queues make range max/min efficient

• Prefix sums turn a nested DP into linear time

A perfect blend of techniques you’ll see again and again in medium–hard problems.

That’s it for Day 82 of my LeetCode challenge 💪
See you tomorrow 🚀

Happy Coding 👨‍💻