LeetCode 2966 - Divide Array Into Arrays With Max Difference

The problem asks us to divide an integer array nums of size n (where n is guaranteed to be a multiple of 3) into smaller arrays of exactly size 3, such that within each array, the difference between the largest and smallest element does not exceed a given integer k.

leetcodemediumarraygreedysorting

LeetCode Problem 2966

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to divide an integer array nums of size n (where n is guaranteed to be a multiple of 3) into smaller arrays of exactly size 3, such that within each array, the difference between the largest and smallest element does not exceed a given integer k. The goal is to return a valid 2D array that satisfies this condition, or an empty array if no valid division exists.

The input nums can have up to 10^5 elements, each element between 1 and 10^5, and k can also range up to 10^5. The constraints indicate that the solution must be efficient-likely O(n log n) or O(n)-because a brute-force approach that examines all combinations of triplets is infeasible for the largest inputs.

Key edge cases include arrays where all elements are identical (trivial division), arrays where one large outlier prevents any valid grouping, and cases where multiple divisions are possible, since the problem allows returning any valid division.

Approaches

The brute-force approach would attempt to generate all possible triplet combinations from the array and check if their maximum difference is within k. For each triplet, we would remove the elements from nums and recurse to form the remaining groups. This guarantees correctness but has factorial complexity, O((n choose 3) * (n/3)!), which is infeasible for n up to 10^5.

The optimal approach relies on sorting and a greedy strategy. By sorting the array, the elements that are closest in value are adjacent. Therefore, we can form triplets consecutively from the sorted array and check if the difference between the first and last element of each triplet is less than or equal to k. If any triplet fails this condition, no valid division exists. This approach works because sorting ensures that the smallest differences are adjacent, which maximizes the chance to satisfy the condition greedily.

Approach Time Complexity Space Complexity Notes
Brute Force O((n choose 3) * (n/3)!) O(n) Generates all triplets and recursively forms groups
Optimal O(n log n) O(n) Sorts the array and greedily forms triplets

Algorithm Walkthrough

  1. Sort the array nums in ascending order. Sorting ensures that elements close in value are adjacent, which maximizes the chance of forming valid triplets.
  2. Initialize an empty list result to store the final triplets.
  3. Iterate over the sorted array in steps of 3, extracting each consecutive triplet (nums[i], nums[i+1], nums[i+2]).
  4. Check if the difference between the largest and smallest element in the triplet, i.e., nums[i+2] - nums[i], is less than or equal to k.
  5. If the condition is satisfied, append the triplet to result. Otherwise, return an empty array immediately because no valid division exists.
  6. After iterating through all elements, return result.

Why it works: Sorting guarantees that the smallest possible differences are adjacent. By forming triplets consecutively, we minimize the chance that any triplet will exceed k. If a consecutive triplet fails the condition, no other grouping can succeed because elements further apart in the sorted order will only have larger differences.

Python Solution

from typing import List

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        result = []
        
        for i in range(0, n, 3):
            triplet = nums[i:i+3]
            if triplet[2] - triplet[0] > k:
                return []
            result.append(triplet)
        
        return result

The Python implementation follows the algorithm exactly. The array is sorted first. Then, in a loop stepping by 3, each triplet is extracted. The difference between the largest and smallest element in the triplet is checked. If any triplet violates the condition, an empty list is returned. Otherwise, all valid triplets are appended to result, which is returned at the end.

Go Solution

import "sort"

func divideArray(nums []int, k int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    result := make([][]int, 0, n/3)
    
    for i := 0; i < n; i += 3 {
        if nums[i+2]-nums[i] > k {
            return [][]int{}
        }
        triplet := []int{nums[i], nums[i+1], nums[i+2]}
        result = append(result, triplet)
    }
    
    return result
}

The Go version mirrors the Python logic. We sort nums, iterate in steps of 3, check the difference between the largest and smallest of each triplet, and append valid triplets to the result. If a triplet fails the condition, an empty 2D slice is returned.

Worked Examples

Example 1

Input: nums = [1,3,4,8,7,9,3,5,1], k = 2

After sorting: [1,1,3,3,4,5,7,8,9]

Iteration:

i triplet max - min valid?
0 [1,1,3] 2 yes
3 [3,4,5] 2 yes
6 [7,8,9] 2 yes

Output: [[1,1,3],[3,4,5],[7,8,9]]

Example 2

Input: nums = [2,4,2,2,5,2], k = 2

After sorting: [2,2,2,2,4,5]

Iteration:

i triplet max - min valid?
0 [2,2,2] 0 yes
3 [2,4,5] 3 no

Output: []

Example 3

Input: nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14

After sorting: [2,2,2,4,5,5,5,5,7,7,8,8,9,9,10,11,12,12]

All consecutive triplets satisfy max - min ≤ 14, so the valid grouping is returned.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; iterating over the array is O(n)
Space O(n) Space for storing the resulting 2D array

Sorting ensures the optimal grouping of close elements, and the extra space is only used for the final triplets.

Test Cases

# Provided examples
assert Solution().divideArray([1,3,4,8,7,9,3,5,1], 2) == [[1,1,3],[3,4,5],[7,8,9]]
assert Solution().divideArray([2,4,2,2,5,2], 2) == []
assert Solution().divideArray([4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], 14) == [[2,2,2],[4,5,5],[5,5,7],[7,8,8],[9,9,10],[11,12,12]]

# Edge cases
assert Solution().divideArray([1,1,1], 0) == [[1,1,1]]  # minimal size
assert Solution().divideArray([1,2,3,4,5,6], 1) == []  # cannot form valid triplets
assert Solution().divideArray([5,5,5,5,5,5], 0) == [[5,5,5],[5,5,5]]  # identical elements
Test Why
[1,3,4,8,7,9,3,5,1], k=2 Typical valid division
[2,4,2,2,5,2], k=2 No valid division possible
[4,2,...,11], k=14 Large array with valid division
[1,1,1], k=0 Minimal array size
[1,2,3,4,5,6], k=1 Impossible due to large differences
[5,5,5,5,5,5], k=0 Identical elements trivial grouping

Edge Cases

All identical elements: If nums contains the same number repeated, any grouping works since the difference is zero. The implementation handles this naturally as the difference check will always pass.

Minimal input size: If n = 3, there is only one triplet. The solution must correctly handle arrays of exactly three elements.

Large outlier: If the array has one element far from the others, the greedy consecutive