Divide Array Into Arrays With Max Difference
Source: leetcode
Difficulty: Medium
Tags: array, greedy, sorting

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. And if there are multiple answers, return **any** of them.


 


**Example 1:**



**Input:** nums \= \[1,3,4,8,7,9,3,5,1], k \= 2


**Output:** \[\[1,1,3],\[3,4,5],\[7,8,9]]


**Explanation:**


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 \= 2


**Output:** \[]


**Explanation:**


Different ways to divide `nums` into 2 arrays of size 3 are:


- \[\[2,2,2],\[2,4,5]] (and its permutations)
- \[\[2,2,4],\[2,2,5]] (and its permutations)


Because there are four 2s there will be an array with the elements 2 and 5 no matter how we divide it. since `5 - 2 = 3 > k`, the condition is not satisfied and so there is no valid division.



**Example 3:**



**Input:** nums \= \[4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k \= 14


**Output:** \[\[2,2,12],\[4,8,5],\[5,9,7],\[7,8,5],\[5,9,10],\[11,12,2]]


**Explanation:**


The difference between any two elements in each array is less than or equal to 14\.



 


**Constraints:**


- `n == nums.length`
- `1 <= n <= 105`
- `n` is a multiple of 3
- `1 <= nums[i] <= 105`
- `1 <= k <= 105`




C++ solution:
#pragma GCC optimize("O3", "unroll-loops")
class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        int size = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> result(size / 3);
        for (int i = 0; i < size / 3; i++) {
            if (nums[3 * i + 2] - nums[3 * i] <= k) {
                result[i] = {nums[3 * i], nums[3 * i + 1], nums[3 * i + 2]};
            } else {
                return {};
            }
        }
        return result;
    }
};
auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();

Go solution:
func divideArray(nums []int, k int) [][]int {
	n := len(nums)
	res:= make([][]int, 0)
	sort.Ints(nums)
	for i := 0; i < n; i += 3 {
		if i+2 < n && nums[i+2]-nums[i] <= k {
			res= append(res, []int{nums[i], nums[i+1], nums[i+2]})
		} else {
			return [][]int{}
		}
	}
	return res
}

Java solution:
class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        List<int[]> res = new ArrayList<>();
        for (int i = 2; i < nums.length; i += 3) {
            if (nums[i] - nums[i - 2] > k) return new int[][]{};
            res.add(new int[]{nums[i - 2], nums[i - 1], nums[i]});
        }
        return res.toArray(new int[res.size()][]);
    }
}

JavaScript solution:
var divideArray = function(nums, k) {
    nums.sort((a, b) => a - b);
    let res = [];
    for (let i = 2; i < nums.length; i += 3) {
        if (nums[i] - nums[i - 2] > k) return [];
        res.push([nums[i - 2], nums[i - 1], nums[i]]);
    }
    return res;
};

Python solution:
class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()     

        if max(i-j for i, j in zip(nums[2::3],nums[::3])) > k: 
            return []
            
        return zip(nums[::3],nums[1::3],nums[2::3])

Ruby solution:
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer[][]}
def divide_array(nums, k)
    nums.sort.each_slice(3).to_a.each do |array|
        return [] if array[-1] - array[0] > k
    end
end