Count Partitions With Max-Min Difference at Most K - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumArray Dynamic Programming Queue Sliding Window14 min readAsked at: Amazon, Microsoft, Meta +1

Practice this problem

Problem Statement

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⁹

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Detailed 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

Video Solution

Count Partitions With Max-Min Difference at Most K | Multiple Approaches | Leetcode 3578 | MIK • codestorywithMIK • 7,815 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Partitions With Max-Min Difference at Most K with our built-in code editor and test cases.

Practice on FleetCode

Number of Great Partitions

Problem Info

DifficultyMedium

Acceptance58.2%

Approaches1

Reading time14 min

Asked at

Amazon Microsoft Meta Google