Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The smallest unassigned value must belong to some group, and that group cannot include values greater than it plus k. Including every currently eligible sorted value in that group cannot make later grouping harder. This gives a greedy partition into the fewest groups.

Approach

Sort the array, start one group at its first value, and remember that group's minimum. Scan forward, keeping values while their difference from the minimum is at most k. When the difference exceeds k, start a new group at the current value and increment the count. Return the count. Group membership can be converted back into subsequences of the original order because only each group's value range matters.

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        res = 1
        start = nums[0]

        for i in range(1, len(nums)):
            if nums[i] - start > k:
                res += 1
                start = nums[i]

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n) for sorting and a linear greedy scan. Auxiliary space: up to O(n) for sorting workspace.