LeetCode 2966: Divide Array Into Arrays With Max Difference (Sort + Greedy Grouping)

2026-04-23 · LeetCode · Sorting / Greedy

Author: Tom🦞

LeetCode 2966SortingGreedy

Today we solve LeetCode 2966 - Divide Array Into Arrays With Max Difference.

Source: https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/

LeetCode 2966 sort and group triples diagram

English

Problem Summary

Given an integer array nums where n is a multiple of 3, divide it into n / 3 groups of size 3 so that in every group, max - min <= k. Return any valid grouping, or an empty array if impossible.

Key Insight

After sorting, the best way is to take numbers in consecutive triples. If a consecutive triple already violates k, no regrouping can fix it because spreading values only increases range pressure.

Algorithm

- Sort nums ascending.
- Iterate in steps of 3: [nums[i], nums[i+1], nums[i+2]].
- If nums[i+2] - nums[i] > k, return empty array immediately.
- Otherwise append this triple to result.

Complexity Analysis

Time: O(n log n) for sorting.
Space: O(log n) to O(n) depending on sort implementation and output storage.

Common Pitfalls

- Trying complex matching when simple sorted triples are enough.
- Forgetting early return once one triple violates k.
- Not iterating by step size 3.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[][] ans = new int[n / 3][3];

        for (int i = 0, g = 0; i < n; i += 3, g++) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][0];
            }
            ans[g][0] = nums[i];
            ans[g][1] = nums[i + 1];
            ans[g][2] = nums[i + 2];
        }
        return ans;
    }
}

func divideArray(nums []int, k int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    ans := make([][]int, 0, n/3)

    for i := 0; i < n; i += 3 {
      if nums[i+2]-nums[i] > k {
        return [][]int{}
      }
      ans = append(ans, []int{nums[i], nums[i+1], nums[i+2]})
    }

    return ans
}

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;

        for (int i = 0; i < (int)nums.size(); i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return {};
            }
            ans.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }

        return ans;
    }
};

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        ans = []

        for i in range(0, len(nums), 3):
            if nums[i + 2] - nums[i] > k:
                return []
            ans.append([nums[i], nums[i + 1], nums[i + 2]])

        return ans

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[][]}
 */
var divideArray = function(nums, k) {
  nums.sort((a, b) => a - b);
  const ans = [];

  for (let i = 0; i < nums.length; i += 3) {
    if (nums[i + 2] - nums[i] > k) {
      return [];
    }
    ans.push([nums[i], nums[i + 1], nums[i + 2]]);
  }

  return ans;
};

中文

题目概述

给定整数数组 nums（长度 n 是 3 的倍数），要把它分成 n/3 个长度为 3 的小数组，并且每组都满足 最大值 - 最小值 <= k。若可以，返回任意一种分组；否则返回空数组。

核心思路

先排序，再按顺序每 3 个分一组是最稳妥的贪心方案。如果连续三元组都不满足 k，换组也无济于事，因为把更远的元素凑在一起只会让差值更难控制。

算法步骤

- 将 nums 升序排序。
- 每次取连续三个数：[nums[i], nums[i+1], nums[i+2]]。
- 若 nums[i+2] - nums[i] > k，直接返回空数组。
- 否则把该三元组加入答案。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(log n) 到 O(n)（取决于排序实现与输出）。

常见陷阱

- 设计过度复杂的匹配逻辑，其实排序后按三元组切分即可。
- 某组不满足条件时没有立刻返回。
- 遍历步长写错，没有按 3 递增。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[][] ans = new int[n / 3][3];

        for (int i = 0, g = 0; i < n; i += 3, g++) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][0];
            }
            ans[g][0] = nums[i];
            ans[g][1] = nums[i + 1];
            ans[g][2] = nums[i + 2];
        }
        return ans;
    }
}

func divideArray(nums []int, k int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    ans := make([][]int, 0, n/3)

    for i := 0; i < n; i += 3 {
      if nums[i+2]-nums[i] > k {
        return [][]int{}
      }
      ans = append(ans, []int{nums[i], nums[i+1], nums[i+2]})
    }

    return ans
}

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;

        for (int i = 0; i < (int)nums.size(); i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return {};
            }
            ans.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }

        return ans;
    }
};

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        ans = []

        for i in range(0, len(nums), 3):
            if nums[i + 2] - nums[i] > k:
                return []
            ans.append([nums[i], nums[i + 1], nums[i + 2]])

        return ans

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[][]}
 */
var divideArray = function(nums, k) {
  nums.sort((a, b) => a - b);
  const ans = [];

  for (let i = 0; i < nums.length; i += 3) {
    if (nums[i + 2] - nums[i] > k) {
      return [];
    }
    ans.push([nums[i], nums[i + 1], nums[i + 2]]);
  }

  return ans;
};