Skip to main content
Talentd

Divide Array Into Arrays With Max Difference - Solution & Explanation

MediumArrayGreedySorting21 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • n is a multiple of 3
  • 1 <= nums[i] <= 105
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC#SwiftDart

Python

Java

C++

Go

TypeScript

Rust

C#

Swift

Dart

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Forming Groups

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.

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).
Space Complexity: O(n) due to allocated space for the resulting groups.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Forming GroupsO(n log n)O(1)Best general solution. Sorting ensures closest values are grouped first.
Greedy Two-Pointer TechniqueO(n log n)O(1)Useful when implementing greedy window grouping after sorting.

Video Solution

Divide Array Into Arrays With Max Difference - Leetcode 2966 - Python • NeetCodeIO • 13,895 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Divide Array Into Arrays With Max Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays