Divide Array Into Arrays With Max Difference - Solution & Explanation

Problem Overview: You are given an integer array nums and a value k. The goal is to divide the array into groups of exactly three elements such that the difference between the maximum and minimum value in each group is at most k. If forming such groups for the entire array is impossible, return an empty array.

Approach 1: Sorting and Forming Groups (Time: O(n log n), Space: O(1) extra)

The key observation: if three numbers can form a valid group, they will be closest together in sorted order. Start by sorting the array using a standard sorting algorithm. Then iterate through the sorted list in steps of three and check whether nums[i+2] - nums[i] ≤ k. Since the array is sorted, nums[i] is the minimum and nums[i+2] is the maximum in that group. If the difference exceeds k, no valid grouping exists because any other combination would only increase the gap. Otherwise, add the three numbers as one group and continue.

This works because sorting clusters close values together, ensuring that if a valid triplet exists, it will appear consecutively. The algorithm performs a single pass after sorting, making it efficient and easy to implement.

Approach 2: Greedy Two-Pointer Technique (Time: O(n log n), Space: O(1))

This approach also starts by sorting the array, then applies a greedy grouping strategy using pointer movement. After sorting, treat the array as a sequence of candidates. Use a pointer i to mark the start of the next group and greedily attempt to include the next two elements (i+1 and i+2). If the difference between the smallest and largest values in this window is within k, record the group and advance the pointer by three.

If the difference exceeds k, a valid grouping is impossible because any later element will only increase the difference. Sorting ensures that the smallest feasible combination is checked first. This greedy reasoning relies on the ordered structure of the array and avoids unnecessary comparisons.

The technique demonstrates how greedy decisions combined with array traversal can solve grouping problems efficiently. Once sorted, each element is processed exactly once.

Recommended for interviews: The sorting + grouping approach is what most interviewers expect. It shows you recognize that ordering simplifies the constraint max - min ≤ k. A brute force attempt would involve checking combinations of three elements, which is inefficient. Sorting first and validating consecutive triplets demonstrates strong algorithmic intuition and leads directly to the optimal O(n log n) solution.