Count Partitions With Max-Min Difference at Most K

Medium
1678.

Count Partitions With Max-Min Difference at Most K

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.

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^4
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countPartitions = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

Hints for Count Partitions With Max-Min Difference at Most K

  1. Hint 1

    Let dp[i] be the number of valid partitions of the first i elements. The last segment is nums[j..i-1] for some j, so dp[i] sums dp[j] over every j whose segment is valid.

  2. Hint 2

    If nums[j..i-1] is valid, so is every shorter segment ending at i - 1. The valid js therefore form one range [L, i - 1], and L never moves left as i grows.

  3. Hint 3

    Track the window's maximum and minimum with two monotonic deques while advancing L, and read dp[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

  1. Set dp[0] = 1 and pre[1] = 1, where pre[i] = dp[0] + ... + dp[i - 1].
  2. For each index i (0-based), push i onto a decreasing deque (for the max) and an increasing deque (for the min).
  3. While max - min > k for the window [L, i], advance L and drop deque fronts that fall out of the window.
  4. Set dp[i + 1] = pre[i + 1] - pre[L] (mod 10^9 + 7) and pre[i + 2] = pre[i + 1] + dp[i + 1].
  5. 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 exceeds 10^9, so max - min fits 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