Problem of The Day: Divide Array Into Arrays With Max Difference

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        res = []
        nums.sort()
        N = len(nums)
        curr = [nums[0]]
        size = N // 3
        for i in range(1, N):
            if nums[i] - nums[i - 1] > k and len(curr) > 1:
                return []
            curr.append(nums[i])
            if len(curr) == 3:
                if curr[-1] - curr[0] > k:
                    return []
                res.append(curr[:])
                curr = []
        return res

Editorial

Approach: Sorting

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