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.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, 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 <= 1000000 <= nums[i] <= 1000000 <= k <= 100000
Hints for Partition Array Such That Maximum Difference Is K
Hint 1
Order inside a subsequence does not matter, so sort first.
Hint 2
Once sorted, a greedy sweep works: open a group at the smallest unassigned value and admit everything within
kof it.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
- 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, updatingstart. - 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 = 0is 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 groupsJava
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