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 109 + 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 * 1041 <= nums[i] <= 1090 <= k <= 109Problem 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.
We define f[i] as the number of ways to partition the first i elements. If an array satisfies that the difference between its maximum and minimum values does not exceed k, then any of its subarrays also satisfies this condition. Therefore, we can use two pointers to maintain a sliding window representing the current subarray.
When we reach the r-th element, we need to find the left pointer l such that the subarray from l to r satisfies that the difference between the maximum and minimum values does not exceed k. We can use an ordered set to maintain the elements in the current window, so that we can quickly get the maximum and minimum values.
Each time we add a new element, we insert it into the ordered set and check the difference between the maximum and minimum values in the current window. If it exceeds k, we move the left pointer l until the condition is satisfied. The number of partition ways ending at the r-th element is f[l - 1] + f[l] + ldots + f[r - 1]. We can use a prefix sum array to quickly calculate this value.
The answer is f[n], where n is the length of the array.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array nums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partition Enumeration | O(n^3) | O(1) | Small inputs or for understanding the constraint and verifying logic |
| DP + Sliding Window + Ordered Set | O(n log n) | O(n) | General solution when balanced trees or multisets are available |
| DP + Sliding Window + Monotonic Queues | O(n) | O(n) | Optimal approach when implementing custom window extrema tracking |
Count Partitions With Max-Min Difference at Most K | Multiple Approaches | Leetcode 3578 | MIK • codestorywithMIK • 7,317 views views
Watch 9 more video solutions →Practice Count Partitions With Max-Min Difference at Most K with our built-in code editor and test cases.
Practice on FleetCode