Problem

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.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6
7

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

1
2
3
4

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 <= 10^5
  • n is a multiple of 3
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^5

Solution

Method 1 – Greedy Grouping After Sorting

Intuition

By sorting the array, the closest numbers are adjacent. Grouping every three consecutive numbers ensures the minimum possible difference within each group. If the difference between the smallest and largest in any group exceeds k, it’s impossible to form valid groups.

Approach

  1. Sort the input array nums.
  2. Iterate through the sorted array in steps of 3.
  • For each group of three, check if the difference between the first and third element is at most k.
  • If yes, add the group to the answer.
  • If not, return an empty array (impossible to divide).
  1. Return the list of groups if all are valid.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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) {
        if (nums[i+2] - nums[i] > k)
           return {};
        ans.push_back({nums[i], nums[i+1], nums[i+2]});
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func divideArray(nums []int, k int) [][]int {
   sort.Ints(nums)
   n := len(nums)
   ans := [][]int{}
   for i := 0; i < n; i += 3 {
      if nums[i+2]-nums[i] > k {
        return [][]int{}
      }
      ans = append(ans, []int{nums[i], nums[i+1], nums[i+2]})
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int groups = n / 3;
        int[][] ans = new int[groups][3];
        for (int i = 0; i < n; i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][];
            }
            ans[i / 3][0] = nums[i];
            ans[i / 3][1] = nums[i + 1];
            ans[i / 3][2] = nums[i + 2];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  fun divideArray(nums: IntArray, k: Int): Array<IntArray> {
    nums.sort()
    val n = nums.size
    val ans = mutableListOf<IntArray>()
    for (i in 0 until n step 3) {
      if (nums[i + 2] - nums[i] > k) {
        return emptyArray()
      }
      ans.add(intArrayOf(nums[i], nums[i + 1], nums[i + 2]))
    }
    return ans.toTypedArray()
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
   def divideArray(self, nums: list[int], k: int) -> list[list[int]]:
      nums.sort()
      ans: list[list[int]] = []
      n = len(nums)
      for i in range(0, n, 3):
        if nums[i+2] - nums[i] > k:
           return []
        ans.append([nums[i], nums[i+1], nums[i+2]])
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
   pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
      nums.sort();
      let n = nums.len();
      let mut ans = Vec::new();
      for i in (0..n).step_by(3) {
        if nums[i+2] - nums[i] > k {
           return Vec::new();
        }
        ans.push(vec![nums[i], nums[i+1], nums[i+2]]);
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n log n) (due to sorting)
  • 🧺 Space complexity: O(n) (for the answer array)