Partition Array Such That Maximum Difference Is K

Partition Array Such That Maximum Difference Is K - Problem

You are given an integer array nums and an integer k. You may partition nums into one or more subsequences such that each element in nums appears in exactly one of the subsequences.

Return the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most k.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: After sorting [1,2,4,6], we can partition into {1,2} (diff=1≤2) and {4,6} (diff=2≤2). Need 2 subsequences.

Example 2 — Single Subsequence

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

› Output: 1

💡 Note: All elements fit in one subsequence since max-min = 3-1 = 2 ≤ k=2.

Example 3 — All Separate

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

› Output: 4

💡 Note: Each element needs its own subsequence since consecutive differences are all > 2.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,6,1,2] and k=2

Process

Sort and group greedily

Output

Minimum 2 subsequences needed

Key Takeaway

🎯 Key Insight: Sorting enables greedy partitioning since we only need to track minimum of current group

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that sorting the array first allows us to use a greedy approach. After sorting, we only need to track the minimum element of the current subsequence and start a new subsequence when the difference exceeds k. Best approach is the greedy method with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach After Sorting	O(n log n)	O(1)	Sort array first, then greedily group consecutive elements within k difference
Brute Force - Try All Partitions	O(2^n)	O(n)	Generate all possible partitions and find minimum with valid subsequences

Greedy Approach After Sorting — Algorithm Steps

Sort the array to group similar values
Iterate through sorted array
Start new subsequence when difference exceeds k
Count total subsequences needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Bring similar values together

Greedy Grouping

Start new group when difference > k

Count Groups

Each group becomes one subsequence

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int n, int k) {
    if (n == 0) return 0;
    
    // Sort the array to group similar values
    qsort(nums, n, sizeof(int), compare);
    
    int subsequences = 1;
    int currentMin = nums[0];
    
    // Greedily assign elements to subsequences
    for (int i = 1; i < n; i++) {
        // If current element can't fit in current subsequence
        if (nums[i] - currentMin > k) {
            // Start a new subsequence
            subsequences++;
            currentMin = nums[i];
        }
    }
    
    return subsequences;
}

int main() {
    char buffer[1000];
    fgets(buffer, sizeof(buffer), stdin);
    
    int nums[100];
    int n = 0;
    char* token = strtok(buffer, "[,]");
    while (token != NULL) {
        if ((token[0] >= '0' && token[0] <= '9') || token[0] == '-') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then single pass through array takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables (sorting is in-place)

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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

Greedy Approach After Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler