Partition Array Such That Maximum Difference Is K — Medium Problem & Solution

Split every element of nums into subsequences so that within each subsequence the difference between the largest and smallest value is at most k.

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, Two Pointers
Asked at: Amazon, Google, Walmart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Split every element of nums into subsequences so that within each subsequence the difference between the largest and smallest value is at most k.

Return the minimum number of subsequences needed.

Example 1

Input: nums = [3,6,1,2,5], k = 2
Output: 2
Explanation: The groups [1,2,3] and [5,6] each span at most 2.

Example 2

Input: nums = [1,2,3], k = 1
Output: 2
Explanation: [1,2] and [3].

Example 3

Input: nums = [2,2,4,5], k = 0
Output: 3
Explanation: With k = 0 each distinct value needs its own group.

Constraints

1 <= nums.length <= 100000
0 <= nums[i] <= 100000
0 <= k <= 100000

How to solve Partition Array Such That Maximum Difference Is K

Sorting makes the optimal grouping contiguous. Then a greedy scan opens a group at the smallest unassigned value and keeps admitting values until one falls outside the span.

Approach

Sort a copy of nums.
Track start, the smallest value of the open group.
For each value, open a new group when it exceeds start + k, updating start.
Return the number of groups opened.

Why it works

Exchange argument: in any optimal grouping, sorting the values and taking contiguous blocks is at least as good, because a group's span depends only on its minimum and maximum. Given contiguity, starting each group at the smallest remaining value and stretching as far as k allows is greedily optimal — delaying a value to a later group can never reduce the count.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Comparing against the previous element rather than the group's first element lets a group drift beyond k.
k = 0 is legal and means a group holds a single distinct value.
Subsequences, not subarrays — which is exactly why sorting is allowed.

Reference solution

Python

from typing import List

def partitionArray(nums: List[int], k: int) -> int:
    s = sorted(nums)
    groups = 0
    start = None
    for x in s:
        if start is None or x - start > k:
            groups += 1
            start = x
    return groups

JavaScript

var partitionArray = function(nums, k) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var groups = 0, start = -1, first = true;
    for (var i = 0; i < s.length; i++) {
        if (first || s[i] - start > k) { groups++; start = s[i]; first = false; }
    }
    return groups;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue