LeetCode #2966 Divide Array Into Arrays With Max Difference Solution & Explanation

LeetCode Problem

You are given an integer array nums of size n and a positive integer k.

Divide the array into one or more arrays of size 3 satisfying the following conditions:

• Each element of nums should be in exactly one array.
• The difference between any two elements in one array is less than or equal to k.

Return a 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

💡Hint 1

Try to use a greedy approach.

💡Hint 2

Sort the array and try to group each 3 consecutive elements.

Solution

In the initial approach, we began by sorting the entire array.

Following that, we employed a while loop to traverse through the array in groups of three elements. Within each group, we examined whether the difference between the first and last elements was within a specified limit (k).

If this condition was met, we added the current three elements to the result array. However, if the difference exceeded the limit for any group, the function returned an empty array.

C# Solution

⚠️Solution1

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

        int curIdx = 0;
        int resCnt = 0;

        while(curIdx<nums.Length-1){
            if(nums[curIdx+2]-nums[curIdx]>k){
                return new int[0][];
            }
            int[]tmp = nums[curIdx..(curIdx+3)];

            res[resCnt] = tmp;
            resCnt++;
            curIdx+=3;
        }

        return res;
    }
}

Faster than 40%, but that still means it can be improved~

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Divide Array Into Arrays With Max Difference – LeetCode

Some Random LeetCode posts