Partition Array Such That Maximum Difference Is K

Medium
764.

Partition Array Such That Maximum Difference Is K

Partition Array Such That Maximum Difference Is K is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Walmart interviews.

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
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 partitionArray = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition Array Such That Maximum Difference Is K — Solution

Partition Array Such That Maximum Difference Is K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Partition Array Such That Maximum Difference Is K is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Walmart interviews.

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

Hints for Partition Array Such That Maximum Difference Is K

  1. Hint 1

    Order inside a subsequence does not matter, so sort first.

  2. Hint 2

    Once sorted, a greedy sweep works: open a group at the smallest unassigned value and admit everything within k of it.

  3. Hint 3

    Close the group at the first value that exceeds start + k.

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

  1. Sort a copy of nums.
  2. Track start, the smallest value of the open group.
  3. For each value, open a new group when it exceeds start + k, updating start.
  4. 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

Java

public static int partitionArray(int[] nums, int k) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int groups = 0, start = 0;
    boolean first = true;
    for (int x : s) {
        if (first || x - start > k) {
            groups++;
            start = x;
            first = false;
        }
    }
    return groups;
}

C++

int partitionArray(vector<int>& nums, int k) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int groups = 0, start = 0;
    bool first = true;
    for (int x : s) {
        if (first || x - start > k) {
            groups++;
            start = x;
            first = false;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms