Divide Array Into Arrays With Max Difference

How it works

When the range of values is bounded, counting sort can be faster than comparison-based sorting. We count occurrences of each number, then iterate through possible values in order, building groups of three. As we form each group, we verify that the difference between the smallest and largest element in the group does not exceed k.

Steps

1. Find the maximum value in the array and create a count array.
2. Count the frequency of each number.
3. Iterate through numbers from 0 to the maximum.
4. For each number with remaining count, add it to the current group.
5. When the group reaches size 3, check if group[2] - group[0] > k. If so, return an empty array.
6. Otherwise, add the group to the result and start a new group.
7. Return all groups.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(n + m)

Where n is the size of the array nums and m is the maximum element in nums.

Things to watch for

Checking Wrong Elements for Difference

The maximum difference in a sorted triplet is between the first and third elements (smallest and largest), not adjacent elements. Checking nums[i+1] - nums[i] misses the actual constraint.

Forgetting to Sort First

The greedy approach only works on sorted arrays. Without sorting, consecutive elements may not be close in value, making it impossible to form valid groups even when solutions exist.

Incorrect Handling of Return Value

When no valid division exists, return an empty 2D array, not None or an array with empty subarrays. The return type matters for correctness.

from typing import List

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        max_num = max(nums)
        count = [0] * (max_num + 1)
        for num in nums:
            count[num] += 1

        res = []
        group = []

        for num in range(max_num + 1):
            while count[num] > 0:
                group.append(num)
                count[num] -= 1

                if len(group) == 3:
                    if group[2] - group[0] > k:
                        return []
                    res.append(group)
                    group = []

        return res

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> count(maxNum + 1, 0);

        for (int& num : nums) {
            count[num]++;
        }

        vector<vector<int>> res;
        vector<int> group;

        for (int num = 0; num <= maxNum; num++) {
            while (count[num] > 0) {
                group.push_back(num);
                count[num]--;

                if (group.size() == 3) {
                    if (group[2] - group[0] > k) {
                        return {};
                    }
                    res.push_back(group);
                    group.clear();
                }
            }
        }

        return res;
    }
};