# Divide Array Into Arrays With Max Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/divide-array-into-arrays-with-max-difference)
Canonical: https://scaleengineer.com/dsa/problems/divide-array-into-arrays-with-max-difference
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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.

**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,2\],\[4,5,5\],\[5,5,7\],\[7,8,8\],\[9,9,10\],\[11,12,12\]\]

**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`

# Approaches
## Brute-Force with Backtracking
This approach attempts to find a valid partition by exploring all possible combinations of forming groups of three from the input array. It uses a recursive backtracking algorithm to generate and test each potential partition. If a partition is found where every group satisfies the maximum difference condition, it is returned. This method is exhaustive but computationally very expensive.
**Time:** O(N!) or similar. The number of ways to partition a set of N items into N/3 subsets of size 3 is `N! / ((3!)^(N/3) * (N/3)!)`, which grows extremely fast. · **Space:** O(N) for the recursion stack depth and to store the `used` array and the current partition being built.
**Pros:** Guaranteed to find a solution if one exists, as it explores the entire search space.
**Cons:** Extremely inefficient with a time complexity that is factorial or exponential, making it infeasible for the problem's constraints.; Complex to implement correctly without bugs.; Will result in a 'Time Limit Exceeded' (TLE) verdict on most platforms.
### Explanation
The fundamental idea is to systematically try every possible way to group the `n` numbers into `n/3` sets of three. A recursive function can be used to implement this. To manage the combinations, we can use a boolean array `used` to keep track of elements that have already been assigned to a group.

The backtracking function would work as follows: find the first unused element, assign it to a new group, then search for two other unused elements to complete the group. For each potential group, we check if it's valid (i.e., `max_element - min_element <= k`). If it is, we add it to our current partition and recurse on the remaining elements. If the recursive call fails to find a complete solution, we backtrack by undoing our choice and trying a different combination of elements for the current group.

While this approach is guaranteed to find a solution if one exists, its performance is extremely poor due to the combinatorial explosion of possibilities. For an array of size `n`, the number of partitions is enormous, making this approach impractical for the given constraints.

Here is a conceptual code skeleton for the backtracking approach:
```java
// This is a conceptual implementation and will be too slow for the given constraints.
class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums); // Sorting helps to prune some branches but doesn't change the worst-case complexity.
        List<int[]> resultGroups = new ArrayList<>();
        boolean[] used = new boolean[n];
        if (canPartition(nums, k, used, resultGroups, 0)) {
            return resultGroups.toArray(new int[0][]);
        } else {
            return new int[0][0];
        }
    }

    private boolean canPartition(int[] nums, int k, boolean[] used, List<int[]> resultGroups, int start) {
        if (resultGroups.size() == nums.length / 3) {
            return true; // Successfully partitioned the whole array.
        }

        // Find the first element not yet used.
        int first_idx = -1;
        for (int i = start; i < nums.length; i++) {
            if (!used[i]) {
                first_idx = i;
                break;
            }
        }

        if (first_idx == -1) return true; // All elements used.

        used[first_idx] = true;
        // Find two other elements to form a group.
        for (int j = first_idx + 1; j < nums.length; j++) {
            if (used[j]) continue;
            for (int l = j + 1; l < nums.length; l++) {
                if (used[l]) continue;

                // Check if the group is valid.
                if (nums[l] - nums[first_idx] <= k) {
                    used[j] = true;
                    used[l] = true;
                    resultGroups.add(new int[]{nums[first_idx], nums[j], nums[l]});

                    if (canPartition(nums, k, used, resultGroups, first_idx + 1)) {
                        return true;
                    }

                    // Backtrack
                    resultGroups.remove(resultGroups.size() - 1);
                    used[l] = false;
                    used[j] = false;
                }
            }
        }

        used[first_idx] = false; // Backtrack
        return false;
    }
}
```
### Algorithm
- 1. Define a recursive backtracking function, e.g., `canPartition(nums, k, used_mask, current_partition)`.
- 2. The base case for the recursion is when all elements have been placed into valid groups. In this case, a solution has been found.
- 3. In the recursive step, find the first available element in `nums`.
- 4. Iterate through all possible pairs of other available elements to form a group of three.
- 5. For each potential group, check if it satisfies the condition `max(group) - min(group) <= k`.
- 6. If the group is valid, add it to the current partition, mark its elements as used, and make a recursive call for the remaining elements.
- 7. If the recursive call returns `false`, backtrack by removing the group and unmarking its elements, then try the next combination.
- 8. If all combinations for the current element are exhausted without success, return `false`.

## Greedy Approach with Sorting
This is a highly efficient and optimal approach that relies on a simple greedy strategy. By first sorting the array, we can group elements that are numerically close to each other. This allows us to check for the condition in a single pass, making the algorithm much faster.
**Time:** `O(N log N)`, where `N` is the number of elements in `nums`. Sorting takes `O(N log N)` time, and the subsequent linear scan takes `O(N)` time. · **Space:** `O(N)` or `O(log N)`. The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives uses a variant of Quicksort which requires `O(log N)` space on average for the recursion stack. The output array itself requires `O(N)` space.
**Pros:** Highly efficient with a time complexity dominated by sorting.; Simple and easy to implement.; Guaranteed to find a solution if one exists due to the greedy choice property.
**Cons:** The `O(N log N)` time complexity for sorting is the main performance factor. For certain special cases of input distributions, a non-comparison sort like counting sort could be faster, but `Arrays.sort` is a general and robust solution.
### Explanation
The core insight is that to satisfy the condition `max - min <= k` for every group, we should try to make the difference within each group as small as possible. Sorting the array `nums` helps achieve this. Once the array is sorted, the smallest elements are at the beginning and the largest at the end.

A greedy strategy can then be applied: iterate through the sorted array and form groups from consecutive elements. We take the first three elements `nums[0], nums[1], nums[2]` to form the first group. Since the array is sorted, `nums[0]` is the minimum and `nums[2]` is the maximum in this group. We only need to check if `nums[2] - nums[0] <= k`. 

If this condition fails, no solution is possible. Why? Because `nums[0]` is the smallest element overall. To form a valid group with `nums[0]`, we must pick two other elements. To minimize the group's difference, we should pick the two smallest available elements, which are `nums[1]` and `nums[2]`. If even this best-case group for `nums[0]` is invalid, no other group containing `nums[0]` can be valid, as any other element choices would lead to an even larger difference. Thus, we can safely conclude no solution exists.

If the condition holds, we form the group and move on to the next three elements `nums[3], nums[4], nums[5]` and repeat the process. If we successfully process the entire array this way, we have found a valid partition.

```java
import java.util.Arrays;

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int n = nums.length;
        // The problem statement guarantees n is a multiple of 3.

        // Sort the array to enable the greedy approach.
        Arrays.sort(nums);

        int[][] result = new int[n / 3][3];

        // Iterate through the sorted array, taking elements three at a time.
        for (int i = 0; i < n; i += 3) {
            // For a group {nums[i], nums[i+1], nums[i+2]}, the min is nums[i]
            // and the max is nums[i+2] because the array is sorted.
            if (nums[i + 2] - nums[i] > k) {
                // If the condition is not met for this group, it's impossible to partition.
                return new int[0][0]; // Return an empty array.
            }
            // If the condition is met, form the group.
            result[i / 3] = new int[]{nums[i], nums[i + 1], nums[i + 2]};
        }

        return result;
    }
}
```
### Algorithm
- 1. Sort the input array `nums` in non-decreasing order.
- 2. Create a 2D array `result` of size `(n/3) x 3` to store the answer.
- 3. Iterate through the sorted array with a step of 3, from `i = 0` to `n-1`.
- 4. In each iteration, consider the triplet `(nums[i], nums[i+1], nums[i+2])`.
- 5. Check if the difference between the largest and smallest element, `nums[i+2] - nums[i]`, is greater than `k`.
- 6. If it is, a valid partition is impossible. Return an empty 2D array.
- 7. If the difference is less than or equal to `k`, the triplet is a valid group. Add it to the `result` array.
- 8. After the loop finishes, return the `result` array.

## Optimized Greedy Approach with Counting Sort
This approach is a further optimization of the greedy strategy. Instead of using a general-purpose comparison-based sort (like Quicksort or Mergesort), it uses Counting Sort. This is possible because the values in the input array are constrained to a manageable range. Counting Sort can sort the array in linear time, making it the most efficient approach overall.
**Time:** `O(N + M)`, where `N` is the number of elements and `M` is the range of values in `nums` (i.e., `maxVal`). This is linear time. · **Space:** `O(N + M)`. `O(M)` for the frequency array used in Counting Sort and `O(N)` for the sorted array and the result array.
**Pros:** Most efficient time complexity (`O(N + M)`), which is linear.; Maintains the simplicity of the greedy logic.
**Cons:** Requires extra space for the frequency array, which can be large if the range of numbers (`M`) is very large.; Only applicable when the range of input values is reasonably small.
### Explanation
This approach follows the same greedy logic as the previous one: sort the array and then form groups of three from consecutive elements. The only difference is the sorting algorithm used.

Given that the numbers in `nums` are within a known range (e.g., `1` to `10^5` as per constraints), we can use Counting Sort for a more efficient sorting step.

**Counting Sort Steps:**
1. Find the maximum value (`maxVal`) in `nums`.
2. Create a frequency map (or an array `counts`) of size `maxVal + 1` to store the count of each number in `nums`.
3. Iterate through `nums` and populate the `counts` array.
4. Reconstruct the sorted array by iterating through the `counts` array. For each number `i` from `0` to `maxVal`, add `i` to the sorted array `counts[i]` times.

After sorting `nums` in `O(N + M)` time (where `M` is the range of values), the rest of the algorithm is identical to the previous greedy approach. We iterate through the now-sorted array, taking three elements at a time, and check if `nums[i+2] - nums[i] <= k`.

This optimization reduces the overall time complexity from `O(N log N)` to `O(N + M)`, which is linear.
```java
import java.util.Arrays;

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            if (num > maxVal) {
                maxVal = num;
            }
        }

        // Use Counting Sort
        int[] counts = new int[maxVal + 1];
        for (int num : nums) {
            counts[num]++;
        }

        int[] sortedNums = new int[n];
        int index = 0;
        for (int i = 0; i <= maxVal; i++) {
            for (int j = 0; j < counts[i]; j++) {
                sortedNums[index++] = i;
            }
        }

        // The rest of the logic is the same as the standard greedy approach
        int[][] result = new int[n / 3][3];
        for (int i = 0; i < n; i += 3) {
            if (sortedNums[i + 2] - sortedNums[i] > k) {
                return new int[0][0];
            }
            result[i / 3] = new int[]{sortedNums[i], sortedNums[i + 1], sortedNums[i + 2]};
        }

        return result;
    }
}
```
### Algorithm
- 1. Determine the range of values in `nums`. Let the maximum value be `maxVal`.
- 2. Create a frequency array, `counts`, of size `maxVal + 1`.
- 3. Populate the `counts` array by iterating through `nums`.
- 4. Overwrite the original `nums` array (or create a new one) with the sorted elements by iterating through the `counts` array. This is the Counting Sort algorithm.
- 5. Proceed with the same greedy grouping strategy as the previous approach: iterate through the sorted `nums` array with a step of 3.
- 6. For each triplet `(nums[i], nums[i+1], nums[i+2])`, check if `nums[i+2] - nums[i] > k`.
- 7. If the condition is violated, return an empty array.
- 8. Otherwise, add the valid group to the result.
- 9. Return the final result array.

# Solutions
### Java

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

```

### CSharp

```csharp
public class Solution {
    public int[][] DivideArray(int[] nums, int k) {
        Array.Sort(nums);
        List < int[] > ans = new List < int[] > ();
        for (int i = 0; i < nums.Length; i += 3) {
            if (i + 2 >= nums.Length) {
                return new int[0][];
            }
            int[] t = new int[] {
                nums[i], nums[i + 1], nums[i + 2]
            };
            if (t[2] - t[0] > k) {
                return new int[0][];
            }
            ans.Add(t);
        }
        return ans.ToArray();
    }
}
```

### CPP

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

```

### Python

```python
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

```