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:
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:
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,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
Explanation:
The difference between any two elements in each array is less than or equal to 14.
Constraints:
n == nums.length1 <= n <= 105n is a multiple of 31 <= nums[i] <= 1051 <= k <= 105Sort the array to ensure that the smallest numbers are adjacent, making it easier to form groups where the maximum difference is less than or equal to k. After sorting, iterate through the array and try to form groups of three. At each step, check if the difference between the first and third numbers in the potential group is less than or equal to k. If yes, form the group; otherwise, return an empty array as it's impossible to meet the requirement.
This C solution first sorts the array using qsort. It then iterates through the sorted array, forming groups of three numbers and ensuring that the difference between the smallest and largest number in each group is ≤ k. If a valid group cannot be formed, it returns 0 indicating failure.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), as no additional space is used beyond the input and output storage.
This approach uses a greedy technique with two pointers to form groups of three elements. Sort the array first. Maintain two pointers, &&&i&&& and &&&j&&&, where &&&i&&& points to the start of a possible group and &&&j&&& iterates over the array to form a group when the criteria are met. When the triplet satisfies the requirement, move to the next possible group.
This C implementation uses a sorted array and a two-pointer technique. Pointers &&&i&&& and &&&j&&& are used to track possible triplets. The solution evaluates whether formed groups satisfy the maximum difference ≤ k. If a triplet exceeds the maximum difference, it raises an error and exits as formation is impractical.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) for sorting, O(n) for the two pointers traversal, making it O(n log n).
Space Complexity: O(n) due to allocated space for the resulting groups.
| Approach | Complexity |
|---|---|
| Sorting and Forming Groups | Time Complexity: O(n log n), due to the sorting step. |
| Greedy Two-Pointer Technique | Time Complexity: O(n log n) for sorting, O(n) for the two pointers traversal, making it O(n log n). |
Divide Array Into Arrays With Max Difference - Leetcode 2966 - Python • NeetCodeIO • 12,507 views views
Watch 9 more video solutions →Practice Divide Array Into Arrays With Max Difference with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor