Count Partitions With Max-Min Difference at Most K solution and explanation
Google
9 more videos on this problem
Count Partitions With Max-Min Difference at Most K | Multiple Approaches | Leetcode 3578 | MIKcodestorywithMIK · 57:07 · 7K views
Count Partitions With Max-Min Difference at Most K | LeetCode 3578 | Complete Intuition ExplainedSanyam IIT Guwahati · 33:13 · 5K views
3578. Count Partitions With Max-Min Difference at Most K | Weekly 453 | 3rd ProblemTech Courses · 20:47 · 3K views
Count Partitions With Max-Min Difference at Most K 🔥 | Leetcode 3578 | Sliding Window + DP + Deque Study Placement · 28:18 · 2K views
3578. Count Partitions With Max-Min Difference at Most K | Leetcode Daily - PythonLeetcode Daily · 9:49 · 1K views
3578. Count Partitions With Max-Min Difference at Most K (Leetcode Medium)Programming Live with Larry · 32:02 · 1K views
Count Partitions With Max-Min Difference at Most K | LeetCode 3578 - Pythonimpoldev · 17:50 · 1K views
Daily Leetcode #2076: Dec 06, 2025 - 3578. Count Partitions With Max-Min Difference at Most KProgramming Live with Larry · 27:10 · 1K views
【每日一题】LeetCode 3578. Count Partitions With Max-Min Difference at Most KHuifeng Guan · 29:46 · 593 views
Count Partitions With Max-Min Difference at Most K | LeetCode 3578 | Java Code | Developer CoderDeveloper Coder · 43:52 · 391 views
The problem
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 <= 109
Approach overview
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.
Solution
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.
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
sl = SortedList()
n = len(nums)
f = [1] + [0] * n
g = [1] + [0] * n
l = 1
for r, x in enumerate(nums, 1):
sl.add(x)
while sl[-1] - sl[0] > k:
sl.remove(nums[l - 1])
l += 1
f[r] = (g[r - 1] - (g[l - 2] if l >= 2 else 0) + mod) % mod
g[r] = (g[r - 1] + f[r]) % mod
return f[n]class Solution {
public int countPartitions(int[] nums, int k) {
final int mod = (int) 1e9 + 7;
TreeMap<Integer, Integer> sl = new TreeMap<>();
int n = nums.length;
int[] f = new int[n + 1];
int[] g = new int[n + 1];
f[0] = 1;
g[0] = 1;
int l = 1;
for (int r = 1; r <= n; r++) {
int x = nums[r - 1];
sl.merge(x, 1, Integer::sum);
while (sl.lastKey() - sl.firstKey() > k) {
if (sl.merge(nums[l - 1], -1, Integer::sum) == 0) {
sl.remove(nums[l - 1]);
}
++l;
}
f[r] = (g[r - 1] - (l >= 2 ? g[l - 2] : 0) + mod) % mod;
g[r] = (g[r - 1] + f[r]) % mod;
}
return f[n];
}
}class Solution {
public:
int countPartitions(vector<int>& nums, int k) {
const int mod = 1e9 + 7;
multiset<int> sl;
int n = nums.size();
vector<int> f(n + 1, 0), g(n + 1, 0);
f[0] = 1;
g[0] = 1;
int l = 1;
for (int r = 1; r <= n; ++r) {
int x = nums[r - 1];
sl.insert(x);
while (*sl.rbegin() - *sl.begin() > k) {
sl.erase(sl.find(nums[l - 1]));
++l;
}
f[r] = (g[r - 1] - (l >= 2 ? g[l - 2] : 0) + mod) % mod;
g[r] = (g[r - 1] + f[r]) % mod;
}
return f[n];
}
};import { AvlTree } from 'datastructures-js';
function countPartitions(nums: number[], k: number): number {
const mod = 1_000_000_007;
const n = nums.length;
const cnt = new Map<number, number>();
const st = new AvlTree<number>((a, b) => a - b);
function insert(x: number) {
const c = (cnt.get(x) || 0) + 1;
cnt.set(x, c);
if (c === 1) {
st.insert(x);
}
}
function erase(x: number) {
const c = cnt.get(x)! - 1;
cnt.set(x, c);
if (c === 0) {
st.remove(x);
}
}
const f = Array(n + 1).fill(0);
const g = Array(n + 1).fill(0);
f[0] = 1;
g[0] = 1;
for (let l = 1, r = 1; r <= n; ++r) {
const x = nums[r - 1];
insert(x);
while (st.max()!.getValue() - st.min()!.getValue() > k) {
erase(nums[l - 1]);
l++;
}
f[r] = (g[r - 1] - (l >= 2 ? g[l - 2] : 0) + mod) % mod;
g[r] = (g[r - 1] + f[r]) % mod;
}
return f[n];
}func countPartitions(nums []int, k int) int {
const mod int = 1e9 + 7
sl := redblacktree.New[int, int]()
merge := func(st *redblacktree.Tree[int, int], x, v int) {
c, _ := st.Get(x)
if c+v == 0 {
st.Remove(x)
} else {
st.Put(x, c+v)
}
}
n := len(nums)
f := make([]int, n+1)
g := make([]int, n+1)
f[0], g[0] = 1, 1
for l, r := 1, 1; r <= n; r++ {
merge(sl, nums[r-1], 1)
for sl.Right().Key-sl.Left().Key > k {
merge(sl, nums[l-1], -1)
l++
}
f[r] = g[r-1]
if l >= 2 {
f[r] = (f[r] - g[l-2] + mod) % mod
}
g[r] = (g[r-1] + f[r]) % mod
}
return f[n]
}use std::collections::BTreeMap;
impl Solution {
pub fn count_partitions(nums: Vec<i32>, k: i32) -> i32 {
const mod_val: i32 = 1_000_000_007;
let n = nums.len();
let mut f = vec![0; n + 1];
let mut g = vec![0; n + 1];
f[0] = 1;
g[0] = 1;
let mut sl = BTreeMap::new();
let mut l = 1;
for r in 1..=n {
let x = nums[r - 1];
*sl.entry(x).or_insert(0) += 1;
while sl.keys().last().unwrap() - sl.keys().next().unwrap() > k {
let val = nums[l - 1];
if let Some(cnt) = sl.get_mut(&val) {
*cnt -= 1;
if *cnt == 0 {
sl.remove(&val);
}
}
l += 1;
}
f[r] = (g[r - 1] - if l >= 2 { g[l - 2] } else { 0 } + mod_val) % mod_val;
g[r] = (g[r - 1] + f[r]) % mod_val;
}
f[n]
}
}Complexity analysis
| 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 |
Frequently asked questions
Is Count Partitions With Max-Min Difference at Most K easy or hard?
This problem is generally rated Medium because the core idea requires combining multiple techniques: sliding window, maintaining window extrema, and dynamic programming. The difficulty comes from correctly counting partitions while ensuring each segment satisfies the max-min constraint.
Count Partitions With Max-Min Difference at Most K Python/Java solution
In Python or Java, the solution usually maintains a sliding window while updating DP states for each index. Python implementations often use collections.deque for monotonic queues, while Java solutions may use ArrayDeque or TreeMap. Both versions compute prefix sums to aggregate valid partition counts efficiently.
How to solve Count Partitions With Max-Min Difference at Most K in O(n)?
Maintain a sliding window where the difference between the maximum and minimum elements stays ≤ k. Use two monotonic deques to track these values while expanding the right pointer and adjusting the left pointer when the constraint breaks. Combine this with DP and a prefix sum array to count valid partitions ending at each index in constant time.
What is the best approach for Count Partitions With Max-Min Difference at Most K?
The most practical solution combines dynamic programming with a sliding window that maintains the maximum and minimum values of the current segment. Using monotonic queues or an ordered set keeps the window valid while computing DP transitions. This reduces the complexity to O(n) with deques or O(n log n) with a balanced tree.
Is Count Partitions With Max-Min Difference at Most K asked at Google/Amazon/Meta?
This style of problem appears frequently in interviews at companies like Google, Amazon, and Meta because it combines sliding window techniques with dynamic programming. Interviewers often expect candidates to reason about maintaining window extrema efficiently and counting valid ranges.
What data structure is used in Count Partitions With Max-Min Difference at Most K?
Typical implementations use either an ordered set (such as a TreeMap or multiset) or two monotonic queues to track the maximum and minimum values inside a sliding window. The counting logic relies on a dynamic programming array and prefix sums to accumulate partition counts efficiently.
What is the time complexity of Count Partitions With Max-Min Difference at Most K?
The optimal implementation runs in O(n) time using dynamic programming with a sliding window and monotonic queues to track the current maximum and minimum. If an ordered set or multiset is used instead, the complexity becomes O(n log n) due to insertion and deletion operations.