Divide Array Into Arrays With Max Difference

main.md

Question

Approach

I first sort the array nums so that elements that are closer in value are grouped together. After sorting, I iterate through the array in chunks of 3 elements since each group must contain exactly 3 numbers. For every group of three consecutive elements, I check if the difference between the maximum and minimum element in that group is less than or equal to k. If all such groups satisfy the condition, I collect them into the result. If I find any group where the difference exceeds k, I immediately return an empty array, since it’s impossible to divide nums as required.

Implementation

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(0, len(nums), 3):
            group = nums[i:i+3]
            if group[-1] - group[0] > k:
                return []
            result.append(group)
        return result

Complexities

• Time: O(n log n)
• Space: O(n)