3578. Count Partitions With Max-Min Difference at Most K
Approach
Sliding window; count partitions ending at each index where max-min ≤ k.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
// Approach: Sliding window; count partitions ending at each index where max-min ≤ k.
// Time: O(n) Space: O(n)
public class Solution
{
public int CountPartitions(int[] nums, int k)
{
const int MOD = 1000000007;
LinkedList<int> maxDq = new LinkedList<int>();
LinkedList<int> minDq = new LinkedList<int>();
int n = nums.Length;
int[] dp = new int[n + 1];
dp[0] = 1;
int left = 0, suffix = 0;
for (int right = 0; right < n; right++)
{
suffix = (suffix + dp[right]) % MOD;
while (maxDq.Count > 0 && nums[maxDq.Last.Value] <= nums[right])
maxDq.RemoveLast();
maxDq.AddLast(right);
while (minDq.Count > 0 && nums[minDq.Last.Value] >= nums[right])
minDq.RemoveLast();
minDq.AddLast(right);
while (nums[maxDq.First.Value] - nums[minDq.First.Value] > k)
{
if (minDq.First.Value == left)
minDq.RemoveFirst();
if (maxDq.First.Value == left)
maxDq.RemoveFirst();
suffix = (suffix - dp[left] + MOD) % MOD;
left++;
}
dp[right + 1] = suffix;
}
return dp[n];
}
}