Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Sorting places nearby values together. Grouping consecutive triples minimizes the spread needed around each successive smallest value. Only a triple's first and last elements need comparison because every other pair has a smaller difference.

Approach

Sort nums, then inspect consecutive blocks of three. If the last value minus the first exceeds k, return an empty array; otherwise append that triple to the result.

To see why a failing block rules out every partition, suppose the block starts at sorted index 3t and its third value is too large. Each of the first 3t + 1 values then needs partners among only the first 3t + 2 values: every later value is more than k above it. Those 3t + 1 values require at least t + 1 complete triples, or 3t + 3 available values, a contradiction. If no block fails, the constructed triples themselves form a valid partition.

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []

        for i in range(2, n, 3):
            df3 = nums[i] - nums[i - 2]
            if df3 > k:
                return []
            res.append([nums[i - 2], nums[i - 1], nums[i]])

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n). Auxiliary space: O(n) in the worst case for built-in sorting, excluding the O(n) returned groups.