[Leetcode] 2966. Divide Array Into Arrays With Max Difference

https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/description/?envType=daily-question&envId=2025-06-18

initial

after thinking for 5 mins, I thought just a simple sort will do the trick. But thinking of whether there can be edge case, I wasnt sure what kind of example will break my logic.

Actually this is a crucial logic of this strat. If we have [a, a+1, a+3, a+4, a+5, a+6] with a given threshold k = 2 and [a,a+1,a+3] cannot form a valid subarray, we can see [a+3, a+4, a+5] does form a valid triplet.

But now we are left with a,a+1, ? and have to find a suitable number. Importantly, due to the sorted order, the remaining numbers are greater than a+3. If the triplet [a, a+1, ?] could not form a valid subarray with a+3, it logically follows that it is impossible for these elements to form a valid subarray with any subsequent number in the array.

sol

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        # 1,1,3,3,4,5,7,8,9

        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 

complexity

n log n time
n//3 space <- wrong! ans stores n elements even though it stores n//3 lists so space is n!!