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.

Description Hints 3 Solution Video 57:07

3578. Count Partitions With Max-Min Difference at Most K

Medium58.2% acceptance4 companies

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 10⁹ + 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 * 10⁴
1 <= nums[i] <= 10⁹
0 <= k <= 10⁹

Asked at 4 companies

Google Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Let dp[idx] be the count of ways to partition the array with the last partition ending at index idx.

Hint 3

Try using a sliding window; we can track the minimum and maximum in the window using deques.

57:07

Still stuck?Read the written solution, or watch a walkthrough.

Open solution