Sponsored
Sponsored
Sort 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.
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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5std::vector<std::vector<int>> divideArrayIntoGroups(std::vector<int>& nums, int k) {
6 std::sort(nums.begin(), nums.end());
7 std::vector<std::vector<int>> result;
8
9 for (size_t i = 0; i < nums.size(); i += 3) {
10 if (i + 2 < nums.size() && nums[i+2] - nums[i] <= k) {
11 result.push_back({nums[i], nums[i+1], nums[i+2]});
12 } else {
13 return {};
14 }
15 }
16 return result;
17}
18
19int main() {
20 std::vector<int> nums = {1,3,4,8,7,9,3,5,1};
21 int k = 2;
22 auto result = divideArrayIntoGroups(nums, k);
23
24 if (result.empty()) {
25 std::cout << "[]" << std::endl;
26 } else {
27 for (const auto& group : result) {
28 std::cout << "[" << group[0] << ", " << group[1] << ", " << group[2] << "]" << std::endl;
29 }
30 }
31
32 return 0;
33}In this C++ solution, the array is sorted using std::sort. We then iterate through the list in steps of three, checking the condition that the maximum difference of elements in each triplet is ≤ k. If at any point a valid trio cannot be formed, it returns an empty vector.
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.
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.
using System.Collections.Generic;
class Program {
public static List<int[]> DivideArrayIntoGroups(int[] nums, int k) {
Array.Sort(nums);
var result = new List<int[]>();
int i = 0, j = 0;
while (j < nums.Length) {
if (j - i + 1 == 3) {
if (nums[j] - nums[i] <= k) {
result.Add(new int[] { nums[i], nums[i+1], nums[j] });
i = j + 1;
j = i;
} else {
return new List<int[]>();
}
} else {
j++;
}
}
return result;
}
static void Main() {
int[] nums = { 1, 3, 4, 8, 7, 9, 3, 5, 1 };
int k = 2;
var result = DivideArrayIntoGroups(nums, k);
if (result.Count == 0) {
Console.WriteLine("[]");
} else {
foreach (var group in result) {
Console.WriteLine("[{0}, {1}, {2}]", group[0], group[1], group[2]);
}
}
}
}This C# code also uses the two-pointer method on a sorted array. It seeks to form triplet groups where all elements comply with ≤ k requirements. When a triplet is not viable, the function returns an empty list, representing failure.