Skip to content

← leetcode

Divide Array Into Arrays With Max Difference

· Medium

LeetCode problem 2966

It is just another greedy problem, where you sort the array, and then subdivide into groups of 3, checking if all the groups you form are valid or not.

This is very similar to tomorrow's problem.

code

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 < nums.size(); i += 3) {
            if (nums[i] + k >= nums[i+2]) {
                ans.push_back({nums[i], nums[i+1], nums[i+2]});
            } else {
                return {};
            }
        }
        return ans;
    }
};

complexity

  • Time: O(log(n)) where n is the size of nums
  • Space: O(n)

time taken

  • 4 minutes and 29 seconds