Count Partitions With Max-Min Difference at Most K - Video Solutions

Problem Overview: You are given an array and an integer k. Count the number of ways to partition the array into contiguous subarrays such that for every subarray the difference between its maximum and minimum element is at most k.

Approach 1: Brute Force Partition Enumeration (O(n^3) time, O(1) space)

Generate every possible partition by choosing cut positions between elements. For each segment, scan the subarray to compute its minimum and maximum and check whether max - min ≤ k. Each validation costs O(n), and there are O(n^2) candidate segments across partitions, which pushes the complexity to roughly O(n^3). This approach is useful only for reasoning about the constraint and verifying small test cases.

Approach 2: Dynamic Programming + Two Pointers + Ordered Set (O(n log n) time, O(n) space)

Define dp[i] as the number of valid ways to partition the prefix ending at index i. While iterating the array, maintain a sliding window [left, right] where the difference between the current maximum and minimum stays ≤ k. Use an ordered set (balanced BST or multiset) to track the current window’s min and max in O(log n). Whenever the window becomes invalid, move the left pointer forward and update the set.

All starting indices between left and right can form a valid last segment ending at right. Use a prefix sum over the DP array to accumulate these counts efficiently. Each step performs ordered set updates and prefix lookups, leading to O(n log n) time.

Approach 3: Dynamic Programming + Sliding Window + Monotonic Queues (O(n) time, O(n) space)

The ordered set can be replaced with two monotonic deques: one decreasing deque for the maximum and one increasing deque for the minimum. These structures maintain window extrema in constant time while the sliding window expands or shrinks. When max - min exceeds k, move the left pointer and pop outdated indices from the deques.

Combine this window with the same DP transition using a running prefix sum. Every index enters and leaves each deque once, so the window maintenance becomes O(n). This produces an optimal linear-time solution and is a classic combination of dynamic programming with monotonic queues.

Recommended for interviews: The dynamic programming + sliding window strategy is what interviewers expect. Starting from the brute force demonstrates understanding of the constraint, but the optimized version using monotonic queues or an ordered set shows strong control over window invariants and DP state transitions.