📦Beginner-Friendly Guide "Divide Array Into Arrays With Max Difference" LeetCode 2966 (C++ | Python | JavaScript)

#programming #cpp #javascript #python

LeetCode 2966 | Medium | Greedy + Sorting

🧠 Problem Summary

You are given:

An integer array nums of size n (where n is a multiple of 3)
A positive integer k

Your task is to divide nums into n / 3 arrays of size 3, such that in each group, the difference between the maximum and minimum elements is at most k.

Return:

A valid 2D array of groups if possible.
Otherwise, return an empty array [].

Multiple valid answers are allowed.

🧩 Intuition

We need to split the array into triplets where max difference ≤ k.

The optimal approach is:

Sort the array: close values come together.
Greedily pick every 3 consecutive elements.
If the difference between the 1st and 3rd in any triplet exceeds k, it's invalid.

This ensures we get the smallest difference across every triplet and maximizes the chance of valid grouping.

🧮 C++ Code (with explanation)

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        const int n = nums.size(), mx = *max_element(nums.begin(), nums.end());
        vector<int> freq(mx + 1, 0);

        for (const int& x : nums)
            freq[x]++;

        vector<vector<int>> ans(n / 3, vector<int>(3));
        int x = 0;

        for (int i = 0; i < n / 3; i++) {
            for (int j = 0; j < 3; j++) {
                while (x <= mx && freq[x] == 0) x++;
                ans[i][j] = x;
                freq[x]--;
            }
            if (ans[i][2] - ans[i][0] > k) return {};
        }

        return ans;
    }
};

// Fast I/O for competitive setup
static const int init = []{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}();

📝 Key Notes:

Frequency counting avoids full sorting, useful for large n and value range.
This approach guarantees lexicographically minimal triplets.
If any group violates the max-min condition, return [].

💻 JavaScript Code

var divideArray = function(nums, k) {
    nums.sort((a, b) => a - b);
    const res = [];

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

    return res;
};

🧠 Key Points:

We use native Array.sort() to sort in non-decreasing order.
We check the difference between the 1st and 3rd in each group after slicing.

🐍 Python Code

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

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

        return res

✅ Final Thoughts

This problem is a strong example of:

Greedy selection after sorting
Ensuring bounded differences in grouped segments
Thinking about minimum difference triplets

By focusing on sorting and sliding over fixed-size windows, the problem becomes both simple and efficient. This template is useful for many array grouping or partitioning tasks with tight constraints.

If you liked this breakdown, leave a ❤️ and follow for more practical algorithm guides!

Happy coding! 🛠️