2966. Divide Array Into Arrays With Max Difference - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting Algorithms - Understanding how sorting brings similar elements together for grouping problems
Greedy Algorithms - Making locally optimal choices (grouping consecutive sorted elements) to achieve a global optimum
Counting Sort - An efficient O(n + k) sorting technique when the range of values is bounded

1. Sorting

Intuition

To minimize the difference within each group of three, we should place elements that are close in value together. Sorting the array achieves this naturally. After sorting, we greedily form groups of three consecutive elements. For each group, we only need to check if the difference between the largest and smallest element (first and third in the triplet) is within k. If any group fails this check, no valid division exists.

Algorithm

Sort the array in ascending order.
Iterate through the array in steps of 3.
For each group of three consecutive elements, check if nums[i+2] - nums[i] > k.
If the condition is violated, return an empty array.
Otherwise, add the triplet to the result.
Return the list of triplets.

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

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

        return res

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

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

        return res;
    }
};

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

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

        return res;
    }
}

public class Solution {
    public int[][] DivideArray(int[] nums, int k) {
        Array.Sort(nums);
        int[][] res = new int[nums.Length / 3][];

        for (int i = 0, idx = 0; i < nums.Length; i += 3, idx++) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[][] {};
            }
            res[idx] = new int[] { nums[i], nums[i + 1], nums[i + 2] };
        }

        return res;
    }
}

class Solution {
    fun divideArray(nums: IntArray, k: Int): Array<IntArray> {
        nums.sort()
        val res = mutableListOf<IntArray>()

        for (i in nums.indices step 3) {
            if (nums[i + 2] - nums[i] > k) {
                return emptyArray()
            }
            res.add(intArrayOf(nums[i], nums[i + 1], nums[i + 2]))
        }

        return res.toTypedArray()
    }
}

impl Solution {
    pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
        nums.sort();
        let mut res = Vec::new();

        for i in (0..nums.len()).step_by(3) {
            if nums[i + 2] - nums[i] > k {
                return vec![];
            }
            res.push(vec![nums[i], nums[i + 1], nums[i + 2]]);
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$ for the output array.

2. Counting Sort

Intuition

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.

Algorithm

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

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

public class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }

        int[] count = new int[max + 1];
        for (int num : nums) {
            count[num]++;
        }

        int[][] res = new int[nums.length / 3][3];
        int[] group = new int[3];
        int i = 0;

        for (int num = 0, idx = 0; num <= max; num++) {
            while (count[num] > 0) {
                group[i++] = num;
                count[num]--;

                if (i == 3) {
                    if (group[2] - group[0] > k) {
                        return new int[][]{};
                    }
                    for (int j = 0; j < 3; j++) {
                        res[idx][j] = group[j];
                    }
                    i = 0;
                    idx++;
                }
            }
        }

        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;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[][]}
     */
    divideArray(nums, k) {
        const max = Math.max(...nums);
        const count = new Array(max + 1).fill(0);

        for (const num of nums) {
            count[num]++;
        }

        const res = [];
        let group = [];

        for (let num = 0; num <= max; num++) {
            while (count[num] > 0) {
                group.push(num);
                count[num]--;

                if (group.length === 3) {
                    if (group[2] - group[0] > k) {
                        return [];
                    }
                    res.push(group);
                    group = [];
                }
            }
        }

        return res;
    }
}

public class Solution {
    public int[][] DivideArray(int[] nums, int k) {
        int max = 0;
        foreach (int num in nums) {
            max = Math.Max(max, num);
        }

        int[] count = new int[max + 1];
        foreach (int num in nums) {
            count[num]++;
        }

        int[][] res = new int[nums.Length / 3][];
        int[] group = new int[3];
        int i = 0, idx = 0;

        for (int num = 0; num <= max; num++) {
            while (count[num] > 0) {
                group[i++] = num;
                count[num]--;

                if (i == 3) {
                    if (group[2] - group[0] > k) {
                        return new int[][] {};
                    }
                    res[idx++] = new int[] { group[0], group[1], group[2] };
                    i = 0;
                }
            }
        }

        return res;
    }
}

func divideArray(nums []int, k int) [][]int {
    maxNum := 0
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }

    count := make([]int, maxNum+1)
    for _, num := range nums {
        count[num]++
    }

    res := [][]int{}
    group := []int{}

    for num := 0; num <= maxNum; num++ {
        for count[num] > 0 {
            group = append(group, num)
            count[num]--

            if len(group) == 3 {
                if group[2]-group[0] > k {
                    return [][]int{}
                }
                res = append(res, group)
                group = []int{}
            }
        }
    }

    return res
}

class Solution {
    fun divideArray(nums: IntArray, k: Int): Array<IntArray> {
        val maxNum = nums.max()
        val count = IntArray(maxNum + 1)

        for (num in nums) {
            count[num]++
        }

        val res = mutableListOf<IntArray>()
        val group = mutableListOf<Int>()

        for (num in 0..maxNum) {
            while (count[num] > 0) {
                group.add(num)
                count[num]--

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

        return res.toTypedArray()
    }
}

class Solution {
    func divideArray(_ nums: [Int], _ k: Int) -> [[Int]] {
        let maxNum = nums.max()!
        var count = [Int](repeating: 0, count: maxNum + 1)

        for num in nums {
            count[num] += 1
        }

        var res = [[Int]]()
        var group = [Int]()

        for num in 0...maxNum {
            while count[num] > 0 {
                group.append(num)
                count[num] -= 1

                if group.count == 3 {
                    if group[2] - group[0] > k {
                        return []
                    }
                    res.append(group)
                    group = []
                }
            }
        }

        return res
    }
}

impl Solution {
    pub fn divide_array(nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
        let max_num = *nums.iter().max().unwrap() as usize;
        let mut count = vec![0i32; max_num + 1];

        for &num in &nums {
            count[num as usize] += 1;
        }

        let mut res = Vec::new();
        let mut group = Vec::new();

        for num in 0..=max_num {
            while count[num] > 0 {
                group.push(num as i32);
                count[num] -= 1;

                if group.len() == 3 {
                    if group[2] - group[0] > k {
                        return vec![];
                    }
                    res.push(group.clone());
                    group.clear();
                }
            }
        }

        res
    }
}

Time & Space 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$ .

Common Pitfalls

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.

# Wrong: Checking adjacent differences
for i in range(0, len(nums), 3):
    if nums[i+1] - nums[i] > k or nums[i+2] - nums[i+1] > k:
        return []

# Correct: Check first and third elements
for i in range(0, len(nums), 3):
    if nums[i+2] - nums[i] > k:
        return []

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.

# Wrong: Missing sort
def divideArray(nums, k):
    res = []
    for i in range(0, len(nums), 3):
        if nums[i+2] - nums[i] > k:  # Not meaningful without sorting!
            return []
        res.append(nums[i:i+3])
    return res

# Correct: Sort first
def divideArray(nums, k):
    nums.sort()  # Critical step!
    res = []
    for i in range(0, len(nums), 3):
        if nums[i+2] - nums[i] > k:
            return []
        res.append(nums[i:i+3])
    return res

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.

// Wrong: Returning null
if (nums[i + 2] - nums[i] > k) {
    return null;  // Incorrect type!
}

// Wrong: Returning array with empty element
return new int[][]{ {} };

// Correct: Return empty 2D array
if (nums[i + 2] - nums[i] > k) {
    return new int[][]{};
}