medium Divide Array Into Arrays With Max Difference

Problem Statement

You are given an array nums containing n integers and a positive integer k.

Divide the nums into arrays of size 3 such that it satisfies the below conditions:

• Each element of nums should be in exactly one array.
• The difference between any two elements of a single array should be less than or equal to k.

Return a 2D array of these subarrays. If no such division is possible, return an empty array.

Examples

Example 1:

• Input: nums = [2, 6, 4, 9, 3, 7, 3, 4, 1], k = 3
• Expected Output: [[1,2,3],[3,4,4],[6,7,9]]
• Explanation: The three groups [1, 2, 3], [3, 4, 4] and [6, 7, 9] all have elements with differences ≤ k. For the group [1, 2, 3] the maximum difference between elements is 2. For the group [3, 4, 4], the maximum difference is 1, and for [6, 7, 9], it's 3, all of which satisfy the condition.

Example 2:

• Input: nums = [10, 12, 15, 20, 25, 30], k = 10
• Expected Output: [[10, 12, 15], [20, 25, 30]]
• Explanation: Here, the two groups have maximum differences of 5 and 10 respectively, which are less than or equal to k, thus meeting the criteria perfectly.

Example 3:

• Input: nums = [1, 2, 4, 5, 9, 10], k = 1
• Expected Output: []
• Explanation: It is not possible to divide the nums in subarrays as the value of the k is equal to 1.

Constraints:

• n == nums.length
• 1 <= n <= 10⁵
• n is a multiple of 3.

Solution

To solve this problem, we will first sort the array to ensure that elements that are close to each other numerically are also close in index. This sorting will make it easier to find subarrays where the difference between the maximum and minimum values does not exceed k.

After sorting, we'll iterate over the array and group every three consecutive elements into a subarray, checking if they satisfy the condition. This approach is effective because sorting brings elements with smaller differences together, which simplifies the process of forming the required subarrays. By processing every three elements as a group, we ensure each group is checked for the condition independently.

Step-by-Step Algorithm

1. Sort the Array: Begin by sorting the array nums. Sorting is crucial as it places elements in ascending order, making it simpler to form groups with small differences.
2. Initialize Variables: Create an empty list result to store the final groups.
3. Iterate and Group Elements: Iterate through the sorted list with a step of three (i.e., consider every three elements). For each triplet:
   • Check if the difference between the maximum and minimum elements in this triplet is less than or equal to k.
   • If it is, append this triplet to result.
   • If not, and if any triplet fails this condition, return an empty list as it indicates it's not possible to satisfy the condition with the given k.
4. Return Result: After processing all possible triplets, return the result list.

Algorithm Walkthrough

Let's take nums = [1, 2, 4, 5, 9, 10] and k = 2:

1. Start with the Input:

   • Original array: nums = [2, 6, 4, 9, 3, 7, 3, 4, 1]
   • Maximum allowed difference (k): 3

2. Step 1: Sort the Array

   • First, we sort the array to bring elements that are numerically close to each other nearer in the array, making it easier to group them.
   • Sorted array: nums = [1, 2, 3, 3, 4, 4, 6, 7, 9]

3. Step 2: Initialize the Result List

   • We initialize an empty list result that will store the final groups of subarrays.

4. Step 3: Iterate Through the Array in Groups of Three

   • We iterate over the array with a step of three, grouping every three consecutive elements together, and check if they meet the criteria.
   • First Group: [1, 2, 3]
     • Check the difference between the maximum and minimum values: max(1, 2, 3) - min(1, 2, 3) = 3 - 1 = 2
     • Since 2 is less than or equal to k, this group is valid. Add [1, 2, 3] to result.
   • Second Group: [3, 4, 4]
     • Check the difference: max(3, 4, 4) - min(3, 4, 4) = 4 - 3 = 1
     • 1 is less than or equal to k, so this group is also valid. Add [3, 4, 4] to result.
   • Third Group: [6, 7, 9]
     • Check the difference: max(6, 7, 9) - min(6, 7, 9) = 9 - 6 = 3
     • 3 is equal to k, hence this group is valid as well. Add [6, 7, 9] to result.

5. Step 4: Return the Result

   • All iterations are complete, and all groups checked have met the condition. The final result list is:
     • [[1, 2, 3], [3, 4, 4], [6, 7, 9]]

Code

public class Solution {

  // Method to divide the array into subarrays with max difference <= k
  public List<List<Integer>> divideArray(int[] nums, int k) {
    Arrays.sort(nums); // Sort the array to bring closer elements near each other
    List<List<Integer>> result = new ArrayList<>();

    // Iterate over the array in steps of 3 since each subarray must contain exactly 3 elements
    for (int i = 0; i <= nums.length - 3; i += 3) {
      // Check if the max difference within the current triplet is within the allowed limit k
      if ((nums[i + 2] - nums[i]) <= k) {
        List<Integer> subgroup = Arrays.asList(
          nums[i],
          nums[i + 1],
          nums[i + 2]
        );
        result.add(subgroup); // Add the valid group to the result
      } else {
        return new ArrayList<>(); // Return an empty list if any group fails the condition
      }
    }

    return result; // Return the final grouped list
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    int[] nums1 = { 2, 6, 4, 9, 3, 7, 3, 4, 1 };
    int k1 = 3;
    System.out.println("Example 1 Output: " + sol.divideArray(nums1, k1));

    // Example 2
    int[] nums2 = { 10, 12, 15, 20, 25, 30 };
    int k2 = 10;
    System.out.println("Example 2 Output: " + sol.divideArray(nums2, k2));

    // Example 3
    int[] nums3 = { 1, 2, 4, 5, 9, 10 };
    int k3 = 2;
    System.out.println("Example 3 Output: " + sol.divideArray(nums3, k3));
  }
}

Complexity Analysis

Time Complexity

• The total time complexity of the divideArray method is dominated by the sorting step, making it .

Space Complexity

• The space complexity of the solution is for the output list result which holds up to (n/3) subarrays, each containing three integers.