Count Partitions With Max-Min Difference at Most K

Count Partitions With Max-Min Difference at Most K - Problem

Array Dynamic Programming Queue Sliding Window Prefix Sum Monotonic Queue Medium

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^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,6,1,2], k = 2

› Output: 1

💡 Note: Only one valid partition: [4,6] | [1,2]. First segment has max-min = 6-4 = 2 ≤ 2. Second segment has max-min = 2-1 = 1 ≤ 2.

Example 2 — Multiple Partitions

$ Input: nums = [1,3,1], k = 2

› Output: 2

💡 Note: Two valid partitions: [1,3,1] (max-min = 3-1 = 2 ≤ 2) or [1,3] | [1] (first: 3-1=2≤2, second: 1-1=0≤2).

Example 3 — Single Element

$ Input: nums = [5], k = 1

› Output: 1

💡 Note: Only one element, so only one partition [5] with max-min = 5-5 = 0 ≤ 1.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁵
0 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,6,1,2] with constraint k=2

Check Partitions

Test all ways to split into contiguous segments

Count Valid

Count partitions where each segment has max-min ≤ k

Key Takeaway

🎯 Key Insight: Use dynamic programming to count valid partitions by trying all segments ending at each position

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use dynamic programming where dp[i] represents the number of ways to partition nums[0..i-1]. For each position, we try all valid segments ending at that position. The optimized approach expands segments incrementally while tracking min/max values efficiently. Best approach is Optimized DP with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(2^n × n)	O(n)	Generate all possible partitions and count valid ones
Dynamic Programming	O(n³)	O(n)	Build solutions incrementally using DP state transitions
Optimized DP with Efficient Min/Max	O(n²)	O(n)	Optimize min/max computation using expanding window technique

Brute Force - Try All Partitions — Algorithm Steps

Generate all possible partition points
For each partition, check if all segments are valid
Count partitions where every segment has max-min ≤ k

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Try all possible split points

Validate Segments

Check max-min ≤ k for each segment

Count Valid

Count partitions where all segments are valid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MOD 1000000007

int isValidSegment(int* nums, int start, int end, int k) {
    int minVal = nums[start], maxVal = nums[start];
    for (int i = start; i <= end; i++) {
        if (nums[i] < minVal) minVal = nums[i];
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    return maxVal - minVal <= k;
}

int countPartitions(int* nums, int n, int k, int index, int partition[][2], int partSize) {
    if (index == n) {
        for (int i = 0; i < partSize; i++) {
            if (!isValidSegment(nums, partition[i][0], partition[i][1], k)) return 0;
        }
        return 1;
    }
    
    int total = 0;
    // Extend last segment
    if (partSize > 0) {
        int oldEnd = partition[partSize-1][1];
        partition[partSize-1][1] = index;
        total = (total + countPartitions(nums, n, k, index+1, partition, partSize)) % MOD;
        partition[partSize-1][1] = oldEnd;
    }
    
    // Start new segment
    partition[partSize][0] = index;
    partition[partSize][1] = index;
    total = (total + countPartitions(nums, n, k, index+1, partition, partSize+1)) % MOD;
    
    return total;
}

int solution(int* nums, int n, int k) {
    int partition[1000][2];
    return countPartitions(nums, n, k, 0, partition, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n possible partitions, each taking O(n) to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler