Divide Array Into Arrays With Max Difference solution and explanation
Google
9 more videos on this problem
Divide Array Into Arrays With Max Difference - Leetcode 2966 - PythonNeetCodeIO · 6:24 · 13K views
Divide Array Into Arrays With Max Difference| Why Sorting | Google | Leetcode 2966codestorywithMIK · 16:02 · 8K views
Leetcode | 2966. Divide Array Into Arrays With Max Difference | Medium | Java SolutionDeveloper Docs · 8:04 · 863 views
Solving LeetCode 2966 Divide Array Into Arrays With Max Difference | Greedy | Google Interview QuesCode Harmony · 9:53 · 439 views
Daily Leetcode #1402: Feb 01, 2024 - 2966. Divide Array Into Arrays With Max DifferenceProgramming Live with Larry · 11:17 · 273 views
HOW TO Divide Array Into Arrays With Max Difference - Leetcode 2966Lit Code · 5:33 · 163 views
2966. Divide Array Into Arrays With Max Difference | Leetcode Daily - PythonLeetcode Daily · 5:34 · 147 views
LeetCode 2966 - Divide Array Into Arrays With Max Difference - PythonAlpha-Code · 4:49 · 90 views
2966. Divide Array Into Arrays With Max Difference | leetcode 2966 | optimised solution | javacodingX krishna · 18:40 · 81 views
Divide Array Into Arrays With Max Difference | Leetcode 2966 | Java Code | Developer CoderDeveloper Coder · 14:11 · 73 views
The problem
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:
- The difference between any two elements in one array is less than or equal to
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:
- [[2,2,2],[2,4,5]] (and its permutations)
- [[2,2,4],[2,2,5]] (and its permutations)
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 <= 105nis a multiple of 31 <= nums[i] <= 1051 <= k <= 105
Approach overview
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.
Approach 1: Sorting and Forming Groups
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.
def divide_array_into_groups(nums, k):
nums.sort()
result = []
for i in range(0, len(nums), 3):
if i + 2 < len(nums) and nums[i + 2] - nums[i] <= k:
result.append([nums[i], nums[i+1], nums[i+2]])
else:
return []
return result
# Example usage
nums = [1,3,4,8,7,9,3,5,1]
k = 2
print(divide_array_into_groups(nums, k))import java.util.*;
public class DivideArray {
public static List<int[]> divideArrayIntoGroups(int[] nums, int k) {
Arrays.sort(nums);
List<int[]> result = new ArrayList<>();
for (int i = 0; i < nums.length; i += 3) {
if (i + 2 < nums.length && nums[i+2] - nums[i] <= k) {
result.add(new int[]{nums[i], nums[i+1], nums[i+2]});
} else {
return Collections.emptyList();
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1,3,4,8,7,9,3,5,1};
int k = 2;
List<int[]> result = divideArrayIntoGroups(nums, k);
if (result.isEmpty()) {
System.out.println("[]");
} else {
for (int[] group : result) {
System.out.println(Arrays.toString(group));
}
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::vector<int>> divideArrayIntoGroups(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
for (size_t i = 0; i < nums.size(); i += 3) {
if (i + 2 < nums.size() && nums[i+2] - nums[i] <= k) {
result.push_back({nums[i], nums[i+1], nums[i+2]});
} else {
return {};
}
}
return result;
}
int main() {
std::vector<int> nums = {1,3,4,8,7,9,3,5,1};
int k = 2;
auto result = divideArrayIntoGroups(nums, k);
if (result.empty()) {
std::cout << "[]" << std::endl;
} else {
for (const auto& group : result) {
std::cout << "[" << group[0] << ", " << group[1] << ", " << group[2] << "]" << std::endl;
}
}
return 0;
}function divideArrayIntoGroups(nums, k) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length; i+=3) {
if (i + 2 < nums.length && nums[i+2] - nums[i] <= k) {
result.push([nums[i], nums[i+1], nums[i+2]]);
} else {
return [];
}
}
return result;
}
// Example usage
const nums = [1,3,4,8,7,9,3,5,1];
const k = 2;
console.log(divideArrayIntoGroups(nums, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
void divideArrayIntoGroups(int* nums, int numsSize, int k, int(*result)[3], int* returnSize) {
qsort(nums, numsSize, sizeof(int), compare);
int index = 0;
*returnSize = numsSize / 3;
for (int i = 0; i < numsSize; i += 3) {
if (i + 2 < numsSize && nums[i+2] - nums[i] <= k) {
result[index][0] = nums[i];
result[index][1] = nums[i+1];
result[index][2] = nums[i+2];
index++;
} else {
*returnSize = 0;
return;
}
}
}
int main() {
int nums[] = {1,3,4,8,7,9,3,5,1};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int result[numsSize / 3][3];
divideArrayIntoGroups(nums, numsSize, k, result, &returnSize);
if (returnSize == 0) {
printf("[]\n");
} else {
for (int i = 0; i < returnSize; i++) {
printf("[%d, %d, %d]\n", result[i][0], result[i][1], result[i][2]);
}
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static List<int[]> DivideArrayIntoGroups(int[] nums, int k) {
Array.Sort(nums);
var result = new List<int[]>();
for (int i = 0; i < nums.Length; i += 3) {
if (i + 2 < nums.Length && nums[i + 2] - nums[i] <= k) {
result.Add(new int[] { nums[i], nums[i+1], nums[i+2] });
} else {
return new List<int[]>();
}
}
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(string.Join(", ", group));
}
}
}
}This Python solution sorts the array with sort(), then traverses it to form groups of three numbers. It checks if the absolute difference between the minimum and maximum values in a group is ≤ k. If a valid group cannot be established, an empty list is returned.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), aside from the storage in the result.
Approach 2: Greedy Two-Pointer Technique
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.
def divide_array_into_groups(nums, k):
nums.sort()
result = []
i, j = 0, 0
while j < len(nums):
if j - i + 1 == 3:
if nums[j] - nums[i] <= k:
result.append([nums[i], nums[i+1], nums[j]])
i = j + 1
j = i
else:
return []
j += 1
return result
# Example usage
nums = [1,3,4,8,7,9,3,5,1]
k = 2
print(divide_array_into_groups(nums, k))import java.util.*;
public class DivideArray {
public static List<int[]> divideArrayIntoGroups(int[] nums, int k) {
Arrays.sort(nums);
List<int[]> result = new ArrayList<>();
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 Collections.emptyList();
}
} else {
j++;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1,3,4,8,7,9,3,5,1};
int k = 2;
List<int[]> result = divideArrayIntoGroups(nums, k);
if (result.isEmpty()) {
System.out.println("[]");
} else {
for (int[] group : result) {
System.out.println(Arrays.toString(group));
}
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::vector<int>> divideArrayIntoGroups(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
size_t i = 0, j = 0;
while (j < nums.size()) {
if (j - i + 1 == 3) {
if (nums[j] - nums[i] <= k) {
result.push_back({nums[i], nums[i+1], nums[j]});
i = j + 1;
j = i;
} else {
return {};
}
} else {
++j;
}
}
return result;
}
int main() {
std::vector<int> nums = {1,3,4,8,7,9,3,5,1};
int k = 2;
auto result = divideArrayIntoGroups(nums, k);
if (result.empty()) {
std::cout << "[]" << std::endl;
} else {
for (const auto& group : result) {
std::cout << "[" << group[0] << ", " << group[1] << ", " << group[2] << "]" << std::endl;
}
}
return 0;
}function divideArrayIntoGroups(nums, k) {
nums.sort((a, b) => a - b);
const result = [];
let i = 0, j = 0;
while (j < nums.length) {
if (j - i + 1 === 3) {
if (nums[j] - nums[i] <= k) {
result.push([nums[i], nums[i+1], nums[j]]);
i = j + 1;
j = i;
} else {
return [];
}
}
j++;
}
return result;
}
// Example usage
const nums = [1,3,4,8,7,9,3,5,1];
const k = 2;
console.log(divideArrayIntoGroups(nums, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int** divideArrayIntoGroups(int* nums, int numsSize, int k, int* returnSize) {
if (numsSize % 3 != 0) {
*returnSize = 0;
return NULL;
}
qsort(nums, numsSize, sizeof(int), compare);
int** result = (int**)malloc(sizeof(int*) * (numsSize / 3));
int count = 0;
int i = 0, j = 0;
while (j < numsSize) {
if (j - i + 1 == 3) {
if (nums[j] - nums[i] <= k) {
int* group = (int*)malloc(sizeof(int) * 3);
group[0] = nums[i];
group[1] = nums[i+1];
group[2] = nums[j];
result[count++] = group;
i = j + 1;
j = i;
} else {
free(result);
*returnSize = 0;
return NULL;
}
} else {
j++;
}
}
*returnSize = count;
return result;
}
int main() {
int nums[] = {1,3,4,8,7,9,3,5,1};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int** result = divideArrayIntoGroups(nums, numsSize, k, &returnSize);
if (returnSize == 0) {
printf("[]\n");
} else {
for (int i = 0; i < returnSize; i++) {
printf("[%d, %d, %d]\n", result[i][0], result[i][1], result[i][2]);
free(result[i]);
}
free(result);
}
return 0;
}using System;
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 Python algorithm uses a sorted list and two pointers. It increments &&&i&&& and &&&j&&& to create valid groups of three numbers, ensuring they conform to the ≤ k rule. If they cannot comply, an empty list signals failure.
Time Complexity: O(n log n) due to the sorting phase.
Space Complexity: O(n) in relation to the number of resultant groups stored.
Approach 3: Sorting
First, we sort the array. Then, we take out three elements each time. If the difference between the maximum and minimum values of these three elements is greater than k, then the condition cannot be satisfied, and we return an empty array. Otherwise, we add the array composed of these three elements to the answer array.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array.
function divideArray(nums: number[], k: number): number[][] {
nums.sort((a, b) => a - b);
const ans: number[][] = [];
for (let i = 0; i < nums.length; i += 3) {
const t = nums.slice(i, i + 3);
if (t[2] - t[0] > k) {
return [];
}
ans.push(t);
}
return ans;
}func divideArray(nums []int, k int) [][]int {
sort.Ints(nums)
ans := [][]int{}
for i := 0; i < len(nums); i += 3 {
t := slices.Clone(nums[i : i+3])
if t[2]-t[0] > k {
return [][]int{}
}
ans = append(ans, t)
}
return ans
}class Solution {
func divideArray(_ nums: [Int], _ k: Int) -> [[Int]] {
var sortedNums = nums.sorted()
var ans: [[Int]] = []
for i in stride(from: 0, to: sortedNums.count, by: 3) {
if i + 2 >= sortedNums.count {
return []
}
let t = Array(sortedNums[i..<i+3])
if t[2] - t[0] > k {
return []
}
ans.append(t)
}
return ans
}
}impl Solution {
pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
nums.sort();
let mut ans = Vec::new();
let n = nums.len();
for i in (0..n).step_by(3) {
if i + 2 >= n {
return vec![];
}
let t = &nums[i..i+3];
if t[2] - t[0] > k {
return vec![];
}
ans.push(t.to_vec());
}
ans
}
}class Solution {
List<List<int>> divideArray(List<int> nums, int k) {
nums.sort();
List<List<int>> ans = [];
for (int i = 0; i < nums.length; i += 3) {
if (i + 2 >= nums.length) {
return [];
}
List<int> t = nums.sublist(i, i + 3);
if (t[2] - t[0] > k) {
return [];
}
ans.add(t);
}
return ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Forming Groups | Time Complexity: O(n log n), due to sorting. |
| Greedy Two-Pointer Technique | Time Complexity: O(n log n) due to the sorting phase. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Forming Groups | O(n log n) | O(1) | Best general solution. Sorting ensures closest values are grouped first. |
| Greedy Two-Pointer Technique | O(n log n) | O(1) | Useful when implementing greedy window grouping after sorting. |
Frequently asked questions
Is Divide Array Into Arrays With Max Difference easy or hard?
The problem is rated Medium because the correct insight is recognizing that sorting simplifies the constraint checking. Once the array is sorted, the implementation is straightforward. The challenge lies in identifying that consecutive triplets guarantee the minimal possible difference.
Divide Array Into Arrays With Max Difference Python/Java solution
Most implementations follow the same pattern: sort the array, iterate in steps of three, check if nums[i+2] - nums[i] ≤ k, and append the triplet to the result. This logic translates directly into Python, Java, C++, C#, and JavaScript with identical O(n log n) complexity.
How to solve Divide Array Into Arrays With Max Difference in O(n)?
A true O(n) solution is generally not feasible because the algorithm relies on sorting to ensure correct grouping. Sorting guarantees that the smallest and largest values in each triplet are easy to compare. Without ordering, verifying all possible combinations would require much higher complexity.
What is the best approach for Divide Array Into Arrays With Max Difference?
The optimal approach sorts the array and forms groups of three consecutive elements. After sorting, check whether nums[i+2] - nums[i] ≤ k for every triplet. Sorting ensures the smallest possible difference within each group, making this greedy grouping correct. The overall time complexity is O(n log n) with constant extra space.
Is Divide Array Into Arrays With Max Difference asked at Google/Amazon/Meta?
This type of problem commonly appears in interviews at large tech companies because it tests greedy reasoning and sorting-based optimization. Variants of array grouping and constraint-based partitioning are frequently reported in Amazon and Google interview preparation sets.
What data structure is used in Divide Array Into Arrays With Max Difference?
The primary structure is an array combined with sorting. After sorting, the algorithm processes the array sequentially and groups elements into triplets. No advanced data structures like heaps or hash maps are required.
What is the time complexity of Divide Array Into Arrays With Max Difference?
The dominant operation is sorting the array, which takes O(n log n) time. After sorting, the algorithm scans the array once in groups of three, which is O(n). Space complexity is O(1) if the sort is in-place, excluding the output array.