Divide Array Into Arrays With Max Difference
You are given an integer array nums of size n, where n is a multiple of 3, and a positive integer k.
Divide the array nums into n / 3 arrays of size 3 satisfying the following condition:
- The difference between any two elements in one array is less than or equal to
k.
Return a 2D array containing the arrays. If it is impossible to satisfy the conditions, return an empty array. If there are multiple answers, return any of them.
Example 1
Input
nums = [1,3,4,8,7,9,3,5,1], k = 2Output
[[1,1,3],[3,4,5],[7,8,9]]The difference between any two elements in each array is less than or equal to 2.
Example 2
Input
nums = [2,4,2,2,5,2], k = 2Output
[]No matter how the numbers are divided, one array must contain 2 and 5, and since 5 - 2 = 3 > k, no valid division exists.
Constraints
- n == nums.length
- 1 <= n <= 10^5
- n is a multiple of 3
- 1 <= nums[i] <= 10^5
- 1 <= k <= 10^5