Count Partitions With Max-Min Difference at Most K Solution
Count Partitions With Max-Min Difference at Most K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Partitions With Max-Min Difference at Most K is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Prefix Sum, Sliding Window, Queue, Monotonic Queue
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and an integer k.
Partition nums into one or more non-empty contiguous segments so that in every segment the difference between its maximum and its minimum element is at most k.
Return the number of ways to do this. Since the answer may be large, return it modulo 10^9 + 7.
Example 1
Input: nums = [9,4,1,3,7], k = 4
Output: 6
Explanation: [[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]] and [[9],[4,1,3],[7]].
Example 2
Input: nums = [3,3,4], k = 0
Output: 2
Explanation: [[3],[3],[4]] and [[3,3],[4]].
Example 3
Input: nums = [1,2], k = 5
Output: 2
Explanation: [[1],[2]] and [[1,2]].
Constraints
2 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^90 <= k <= 10^9
Hints for Count Partitions With Max-Min Difference at Most K
Hint 1
Let
dp[i]be the number of valid partitions of the firstielements. The last segment isnums[j..i-1]for somej, sodp[i]sumsdp[j]over everyjwhose segment is valid.Hint 2
If
nums[j..i-1]is valid, so is every shorter segment ending ati - 1. The validjs therefore form one range[L, i - 1], andLnever moves left asigrows.Hint 3
Track the window's maximum and minimum with two monotonic deques while advancing
L, and readdp[L] + ... + dp[i - 1]from a running prefix sum.
How to solve Count Partitions With Max-Min Difference at Most K
The count obeys a simple recurrence over the position of the last cut, and the valid positions for that cut form a sliding window. Monotonic deques maintain the window's max and min, and prefix sums of dp turn each window sum into one subtraction.
Approach
- Set
dp[0] = 1andpre[1] = 1, wherepre[i] = dp[0] + ... + dp[i - 1]. - For each index
i(0-based), pushionto a decreasing deque (for the max) and an increasing deque (for the min). - While
max - min > kfor the window[L, i], advanceLand drop deque fronts that fall out of the window. - Set
dp[i + 1] = pre[i + 1] - pre[L](mod10^9 + 7) andpre[i + 2] = pre[i + 1] + dp[i + 1]. - Return
dp[n].
Why it works
Shrinking a segment can only lower its maximum and raise its minimum, so validity is monotone in the left end: once nums[L..i] is valid, every nums[j..i] with j >= L is valid, and once nums[L..i] is invalid it stays invalid for all larger i. That makes L a two-pointer boundary and the set of valid last-cut positions exactly [L, i].
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The prefix-sum subtraction can go negative modulo
10^9 + 7— add the modulus back. - Values reach
10^9, but their difference never exceeds10^9, somax - minfits a 32-bit integer; adding them would not. - The deques store indices, not values, so you can tell when the front has left the window.
Reference solution
Python
from typing import List
from collections import deque
def countPartitions(nums: List[int], k: int) -> int:
MOD = 10**9 + 7
n = len(nums)
dp = [0] * (n + 1)
dp[0] = 1
pre = [0] * (n + 2)
pre[1] = 1
mx, mn = deque(), deque()
left = 0
for i in range(n):
while mx and nums[mx[-1]] <= nums[i]:
mx.pop()
mx.append(i)
while mn and nums[mn[-1]] >= nums[i]:
mn.pop()
mn.append(i)
while nums[mx[0]] - nums[mn[0]] > k:
left += 1
if mx[0] < left:
mx.popleft()
if mn[0] < left:
mn.popleft()
dp[i + 1] = (pre[i + 1] - pre[left]) % MOD
pre[i + 2] = (pre[i + 1] + dp[i + 1]) % MOD
return dp[n]Java
public static int countPartitions(int[] nums, int k) {
final long MOD = 1000000007L;
int n = nums.length;
long[] dp = new long[n + 1], pre = new long[n + 2];
dp[0] = 1;
pre[1] = 1;
ArrayDeque<Integer> mx = new ArrayDeque<>(), mn = new ArrayDeque<>();
int left = 0;
for (int i = 0; i < n; i++) {
while (!mx.isEmpty() && nums[mx.peekLast()] <= nums[i]) mx.pollLast();
mx.addLast(i);
while (!mn.isEmpty() && nums[mn.peekLast()] >= nums[i]) mn.pollLast();
mn.addLast(i);
while (nums[mx.peekFirst()] - nums[mn.peekFirst()] > k) {
left++;
if (mx.peekFirst() < left) mx.pollFirst();
if (mn.peekFirst() < left) mn.pollFirst();
}
dp[i + 1] = (pre[i + 1] - pre[left] + MOD) % MOD;
pre[i + 2] = (pre[i + 1] + dp[i + 1]) % MOD;
}
return (int) dp[n];
}C++
int countPartitions(vector<int>& nums, int k) {
const long long MOD = 1000000007LL;
int n = nums.size();
vector<long long> dp(n + 1, 0), pre(n + 2, 0);
dp[0] = 1;
pre[1] = 1;
deque<int> mx, mn;
int left = 0;
for (int i = 0; i < n; i++) {
while (!mx.empty() && nums[mx.back()] <= nums[i]) mx.pop_back();
mx.push_back(i);
while (!mn.empty() && nums[mn.back()] >= nums[i]) mn.pop_back();
mn.push_back(i);
while (nums[mx.front()] - nums[mn.front()] > k) {
left++;
if (mx.front() < left) mx.pop_front();
if (mn.front() < left) mn.pop_front();
}
dp[i + 1] = (pre[i + 1] - pre[left] + MOD) % MOD;
pre[i + 2] = (pre[i + 1] + dp[i + 1]) % MOD;
}
return (int) dp[n];
}JavaScript
var countPartitions = function(nums, k) {
var MOD = 1000000007;
var n = nums.length;
var dp = new Array(n + 1).fill(0);
var pre = new Array(n + 2).fill(0);
dp[0] = 1;
pre[1] = 1;
var mx = [], mn = [], mxHead = 0, mnHead = 0, left = 0;
for (var i = 0; i < n; i++) {
while (mx.length > mxHead && nums[mx[mx.length - 1]] <= nums[i]) mx.pop();
mx.push(i);
while (mn.length > mnHead && nums[mn[mn.length - 1]] >= nums[i]) mn.pop();
mn.push(i);
while (nums[mx[mxHead]] - nums[mn[mnHead]] > k) {
left++;
if (mx[mxHead] < left) mxHead++;
if (mn[mnHead] < left) mnHead++;
}
dp[i + 1] = (pre[i + 1] - pre[left] + MOD) % MOD;
pre[i + 2] = (pre[i + 1] + dp[i + 1]) % MOD;
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming