Question

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:
  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

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;
  }
};

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;
}