2966. Divide Array Into Arrays With Max Difference


Problem Description

In this problem, we're given an array of integers, nums, with a size n and a positive integer k. The objective is to split this array into one or more subarrays where each subarray has exactly 3 elements. There are certain conditions that we have to follow when creating these subarrays. Firstly, each element from the original array must be used once and only once—this means that each element in nums must be put into exactly one subarray. Secondly, for any given subarray, the difference between the largest and smallest values within that subarray can't be greater than k. The task is to return a 2D array with all the constructed subarrays that fit these criteria. If it's not possible to divide the array under these conditions, we must return an empty array. Also, if there are multiple ways to divide the array that fit the requirements, we are free to return any one of them.

Intuition

To solve this problem, a straightforward approach is to first impose an order by sorting the array. Once sorted, we can confidently compare adjacent elements knowing that they represent the nearest possible grouping by value.

After sorting the array, we start taking chunks of three elements at a time from the start since we're required to have subarrays of size three. For each set of three elements, we inspect the difference between the maximum element and the minimum element. Because the array is sorted, these elements will be the first and the last in the chunk.

If the difference exceeds k, then we know it's not possible to divide the array while satisfying the conditions (because a sorted array ensures that this set of three has the smallest possible maximum difference). Therefore, we can terminate early and return an empty array.

If the difference is within k, this grouping is valid, and we can add it to the list of answers. We repeat this process, moving forward in the array by three elements each time until we've successfully created subarrays out of all elements in nums. The solution approach ensures that we consider each element exactly once and check for the condition without any backtracking, thus providing an efficient and correct way of dividing the array into subarrays, or determining if it cannot be done.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation of the solution uses a straightforward algorithm and the basic data structure of arrays (or lists in Python). The key pattern used here is sorting, which is a common first step in a variety of problems to arrange elements in a non-decreasing order.

Here's a step-by-step walk-through of the algorithm, referring to the reference solution approach:

  1. Sort the array: We apply a built-in sorting function to the nums array, rearranging its elements in ascending order. This is a crucial step because it allows us to easily check the difference between the smallest and largest numbers in any subsequent groups of three.

  2. Initialize the answer list: An empty list ans is initialized to store the valid subarrays if we can form them.

  3. Iterate through the array in chunks of three: The sorted nums array is traversed using a for-loop with a step of 3 in range(0, n, 3). Each iteration corresponds to a potential subarray.

  4. Check the difference constraint: In the loop, we take a slice of the array from index i to i + 3, which includes three elements. We then check if the difference between the last element (which is the maximum because of sorting) and the first element (which is the minimum) exceeds k.

    • Violation of the constraint: If this difference is greater than k, we know it is impossible to form a subarray that meets the condition, and therefore an empty array is immediately returned, as it indicates that we cannot divide the array successfully.

    • Constraint satisfied: If the difference does not exceed k, this slice of three elements is a valid subarray, and we add it to the answer list ans.

  5. Return the result: Once the loop has finished and no constraint has been violated, we return the ans list, which contains all successfully formed subarrays.

Throughout this process, no additional data structures are needed other than the input array and the output list. The time complexity of the algorithm is primarily driven by the sorting step, which is typically O(n log n). Since traversing the sorted array and checking for the conditions is done in linear time — O(n) — the total time complexity remains O(n log n).

This solution is elegant in its simplicity, using a commonly understood and implemented pattern of sorting, and demonstrates the power of transforming a problem space to make conditions easier to verify.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the algorithm described above.

Suppose our input array is nums = [4, 8, 2, 7, 6, 1, 9] and k = 3. We want to create subarrays with exactly 3 elements each where the difference between the maximum and smallest values in a subarray should not exceed k. Let's follow the steps:

  1. Sort the array: We sort nums to get [1, 2, 4, 6, 7, 8, 9].

  2. Initialize the answer list: We create an empty list ans = [] to hold our subarrays.

  3. Iterate through the array in chunks of three: We consider subarrays nums[0:3], nums[3:6], and nums[6:9]. These are [1, 2, 4], [6, 7, 8], and the single element [9] left out (which can't form a subarray of size three).

  4. Check the difference constraint:

    • For the first subarray [1, 2, 4], the difference between 4 (max) and 1 (min) is 3, which is equal to k, so this subarray is valid. We add [1, 2, 4] to ans.
    • For the second subarray [6, 7, 8], the difference between 8 (max) and 6 (min) is 2, which is less than k, so this subarray is also valid. We add [6, 7, 8] to ans.
    • The last element [9] cannot form a subarray because there are not enough elements to make a set of three. However, had it been possible to create another subarray with exactly 3 elements, we would have checked it following the same method.
  5. Return the result: We finish the loop and return ans which now contains [[1, 2, 4], [6, 7, 8]].

Here, the key takeaways from the example are:

  • Sorting the array helps us group the nearest numbers together and check if they satisfy the condition.
  • Since the array is processed in sorted order, if any subset of three elements doesn't satisfy the condition, we can immediately conclude that it's not possible to split the array as required, because any other grouping would only increase the difference.
  • The entire process requires only the sorted array and an additional list to store valid subarrays, which is very space-efficient.

The resulting subarrays from our example adhere to the rules of the problem, and the example has demonstrated how the algorithm successfully applies the concepts described in the solution approach.

Solution Implementation

1class Solution:
2    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
3        # Sort the input array to make sure that subarrays with a maximum size difference of k can be found.
4        nums.sort()
5        # Initialize an empty list to store the resulting subarrays.
6        divided_arrays = []
7        # Calculate the length of the input list.
8        nums_length = len(nums)
9      
10        # Iterate over the array in steps of 3, as we want subarrays of size 3.
11        for i in range(0, nums_length, 3):
12            # Generate a subarray of size 3 from the sorted list.
13            subarray = nums[i: i + 3]
14          
15            # Check if the subarray has 3 elements and the maximum size difference condition holds.
16            # If not, return an empty list as the condition cannot be met.
17            if len(subarray) < 3 or subarray[2] - subarray[0] > k:
18                return []
19          
20            # If the condition is met, add the valid subarray to the result list.
21            divided_arrays.append(subarray)
22      
23        # Return the list of all valid subarrays after iterating through the entire input list.
24        return divided_arrays
25
1import java.util.Arrays;
2
3class Solution {
4  
5    /**
6     * Divides an array into smaller sub-arrays of size 3, ensuring the difference between
7     * the maximum and minimum values within each sub-array does not exceed a given value k.
8     *
9     * @param nums the input array of integers to be divided.
10     * @param k    the maximum allowable difference between the largest 
11     *             and smallest numbers in each sub-array.
12     * @return a 2D array where each sub-array has 3 elements and the above condition is met,
13     * or an empty 2D array if the condition cannot be met.
14     */
15    public int[][] divideArray(int[] nums, int k) {
16        // Sort the array to organize numbers and facilitate the process of division
17        Arrays.sort(nums);
18        // Get the length of the input array
19        int n = nums.length;
20        // Initialize the result array with the correct size based on the input array
21        int[][] result = new int[n / 3][];
22        // Iterate through the array, incrementing by 3 each time to create sub-arrays of size 3
23        for (int i = 0; i < n; i += 3) {
24            // Copy a range of the sorted array to form a sub-array of size 3
25            int[] subArray = Arrays.copyOfRange(nums, i, i + 3);
26          
27            // Check if the largest difference in the current sub-array exceeds the limit k
28            if (subArray[2] - subArray[0] > k) {
29                // If it does, return an empty array as the condition can't be met
30                return new int[][] {};
31            }
32          
33            // Assign the sub-array to the correct position in the result array
34            result[i / 3] = subArray;
35        }
36        // Return the duly formed result array
37        return result;
38    }
39}
40
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Method to divide the array into subarrays where
7    // the largest number and smallest number difference is no greater than k
8    // nums: The input array of integers
9    // k: The maximum allowed difference between the largest and smallest
10    // numbers in each subarray
11    std::vector<std::vector<int>> divideArray(std::vector<int>& nums, int k) {
12        // Sort the input array
13        std::sort(nums.begin(), nums.end());
14
15        // Initialize a vector of vectors to store the resulting subarrays
16        std::vector<std::vector<int>> result;
17
18        // The size of the input array
19        int n = nums.size();
20
21        // Iterate over the array in steps of 3 since we are creating trinary subarrays
22        for (int i = 0; i < n; i += 3) {
23            // Check if there are enough elements remaining to create a subarray
24            if (i + 2 >= n) {
25                return {}; // Returning an empty vector as a failure case
26            }
27          
28            // Creating a temporary vector for the current subarray
29            std::vector<int> currentSubarray = { nums[i], nums[i + 1], nums[i + 2] };
30
31            // Check if the difference between the largest and smallest numbers
32            // in the current subarray is greater than k
33            if (currentSubarray[2] - currentSubarray[0] > k) {
34                return {}; // Returning an empty vector as a failure case
35            }
36
37            // Add the current subarray to the result
38            result.emplace_back(currentSubarray);
39        }
40
41        // Return the resultant vector of subarrays
42        return result;
43    }
44};
45
1function divideArray(nums: number[], k: number): number[][] {
2    // Sort the array in non-decreasing order
3    nums.sort((a, b) => a - b);
4
5    // Initialize an empty array to store the groups formed
6    const groups: number[][] = [];
7
8    // Iterate through the sorted array in steps of 3
9    for (let i = 0; i < nums.length; i += k) {
10        // Extract a subarray of size k from the current position
11        const subArray = nums.slice(i, i + k);
12
13        // Check if the difference between max and min of subArray is more than k
14        if (subArray[k - 1] - subArray[0] > k) {
15            // Return an empty array if the condition is not satisfied
16            return [];
17        }
18
19        // If the condition is satisfied, push the subArray into the groups array
20        groups.push(subArray);
21    }
22
23    // Return the groups array containing all subarrays
24    return groups;
25}
26

Time and Space Complexity

The time complexity of the code is O(n \times \log n) because the sort function is used, which typically has a time complexity of O(n \log n) where n is the number of elements in the array to be sorted. After sorting, the code iterates through the list in steps of 3 using a for loop, which is O(n/3). However, this simplifies to O(n) because constants are dropped in Big O notation. Therefore, the combined time complexity, taking the most significant term, remains O(n \log n).

The space complexity of the code is O(n) because a new list ans is created to store the subarrays. The size of ans will be proportional to the size of the input array nums. Thus, as the length of the input array increases, the space consumption of ans scales linearly.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄