2024-02-01 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 1

Description

Divide Array Into Arrays With Max Difference

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.

 

Example 1:

Input: nums = [1,3,4,8,7,9,3,5,1], k = 2
Output: [[1,1,3],[3,4,5],[7,8,9]]
Explanation: We can divide the array into the following arrays: [1,1,3], [3,4,5] and [7,8,9].
The difference between any two elements in each array is less than or equal to 2.
Note that the order of elements is not important.

Example 2:

Input: nums = [1,3,3,2,7,3], k = 3
Output: []
Explanation: It is not possible to divide the array satisfying all the conditions.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • n is a multiple of 3.
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

Solution

class Solution {
public:
  vector<vector<int>> divideArray(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> answer;
    for(int i = 0; i < nums.size(); i += 3) {
      if(nums[i + 2] - nums[i] > k) return {};
      answer.push_back({nums[i], nums[i + 1], nums[i + 2]});
    }
    return answer;
  }
};

// Accepted
// 1115/1115 cases passed (138 ms)
// Your runtime beats 95.85 % of cpp submissions
// Your memory usage beats 39.25 % of cpp submissions (119.5 MB)
Algorithm