# 2966. Divide Array Into Arrays With Max Difference

## Description

You are given an integer array nums of size n and a positive integer k.

Divide the array into one or more arrays of size 3 satisfying the following conditions:

• Each element of nums should be in exactly one array.
• The difference between any two elements in one array is less than or equal to k.

Return a 2D array containing all 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: We can divide the array into the following arrays: [1,1,3], [3,4,5] and [7,8,9].
The difference between any two elements in each array is less than or equal to 2.
Note that the order of elements is not important.


Example 2:

Input: nums = [1,3,3,2,7,3], k = 3
Output: []
Explanation: It is not possible to divide the array satisfying all the conditions.


Constraints:

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

## Solutions

Solution 1: Sorting

First, we sort the array. Then, we take out three elements each time. If the difference between the maximum and minimum values of these three elements is greater than $k$, then the condition cannot be satisfied, and we return an empty array. Otherwise, we add the array composed of these three elements to the answer array.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.

• class Solution {
public int[][] divideArray(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int[][] ans = new int[n / 3][];
for (int i = 0; i < n; i += 3) {
int[] t = Arrays.copyOfRange(nums, i, i + 3);
if (t[2] - t[0] > k) {
return new int[][] {};
}
ans[i / 3] = t;
}
return ans;
}
}

• class Solution {
public:
vector<vector<int>> divideArray(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n; i += 3) {
vector<int> t = {nums[i], nums[i + 1], nums[i + 2]};
if (t[2] - t[0] > k) {
return {};
}
ans.emplace_back(t);
}
return ans;
}
};

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


• func divideArray(nums []int, k int) [][]int {
sort.Ints(nums)
ans := [][]int{}
for i := 0; i < len(nums); i += 3 {
t := slices.Clone(nums[i : i+3])
if t[2]-t[0] > k {
return [][]int{}
}
ans = append(ans, t)
}
return ans
}

• function divideArray(nums: number[], k: number): number[][] {
nums.sort((a, b) => a - b);
const ans: number[][] = [];
for (let i = 0; i < nums.length; i += 3) {
const t = nums.slice(i, i + 3);
if (t[2] - t[0] > k) {
return [];
}
ans.push(t);
}
return ans;
}