Divide Array Into Arrays With Max Difference

medium array greedy sorting

Problem

You are given an integer array nums of size n (a multiple of 3) and a positive integer k. Split nums into n / 3 arrays of size 3 so that the difference between any two elements in a single triple is at most k. Return any valid 2D array, or an empty array if no valid split exists.

Inputnums = [1,3,4,8,7,9,3,5,1], k = 2

Output[[1,1,3],[3,4,5],[7,8,9]]

After sorting, each group of 3 consecutive values has max − min ≤ 2.

nums (comma-separated, length multiple of 3)

def divideArray(nums, k):
    nums.sort()                         # bring close values together
    res = []
    for i in range(0, len(nums), 3):    # walk in blocks of 3
        # sorted block: nums[i] is min, nums[i+2] is max
        if nums[i + 2] - nums[i] > k:
            return []                   # spread too wide -> impossible
        res.append([nums[i], nums[i + 1], nums[i + 2]])
    return res

function divideArray(nums, k) {
  nums.sort((a, b) => a - b);          // numeric sort
  const res = [];
  for (let i = 0; i < nums.length; i += 3) {   // blocks of 3
    // nums[i] is min of the block, nums[i+2] is max
    if (nums[i + 2] - nums[i] > k) {
      return [];                       // spread too wide -> impossible
    }
    res.push([nums[i], nums[i + 1], nums[i + 2]]);
  }
  return res;
}

int[][] divideArray(int[] nums, int k) {
    Arrays.sort(nums);                  // bring close values together
    int[][] res = new int[nums.length / 3][3];
    for (int i = 0; i < nums.length; i += 3) {   // blocks of 3
        // nums[i] is min, nums[i+2] is max of the block
        if (nums[i + 2] - nums[i] > k) {
            return new int[0][];        // impossible
        }
        res[i / 3] = new int[]{nums[i], nums[i + 1], nums[i + 2]};
    }
    return res;
}

vector<vector<int>> divideArray(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());     // bring close values together
    vector<vector<int>> res;
    for (int i = 0; i < (int)nums.size(); i += 3) {   // blocks of 3
        // nums[i] is min, nums[i+2] is max of the block
        if (nums[i + 2] - nums[i] > k) {
            return {};                  // impossible
        }
        res.push_back({nums[i], nums[i + 1], nums[i + 2]});
    }
    return res;
}

Explanation

This is a classic sort-then-greedy problem. Inside a triple, the only thing that matters is the gap between its largest and smallest element — if that gap is ≤ k, then every pairwise difference inside the triple is automatically ≤ k too.

So we want each triple to contain values that are as close together as possible. Sorting does exactly that: it lines numbers up so that the closest values become neighbours. Once sorted, the smartest grouping is simply to take elements 0,1,2, then 3,4,5, and so on — consecutive blocks of three.

Why is this greedy choice optimal? In a sorted array, the smallest value must share a triple with two other numbers. The two cheapest companions for it are the next two smallest values; any other choice would pull in a larger number and only widen the spread. Repeating this argument block by block shows the consecutive grouping is best possible.

For each block, because the array is sorted, nums[i] is the block minimum and nums[i+2] is the block maximum. We only need to check nums[i+2] − nums[i] ≤ k. If even this tightest grouping fails for some block, no grouping can work, so we return an empty array.

Example: [1,3,4,8,7,9,3,5,1] sorts to [1,1,3,3,4,5,7,8,9]. The blocks [1,1,3], [3,4,5], [7,8,9] all have spread 2 ≤ k, giving a valid answer.

Time: O(n log n) Space: O(1) extra (besides output)