3505. Minimum Operations to Make Elements Within K Subarrays Equal LeetCode Solution

In this guide, you will get 3505. Minimum Operations to Make Elements Within K Subarrays Equal LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Make Elements Within K Subarrays Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Operations to Make Elements Within K Subarrays Equal solution in C++
4. Minimum Operations to Make Elements Within K Subarrays Equal solution in Java
5. Minimum Operations to Make Elements Within K Subarrays Equal solution in Python
6. Additional Resources

Problem Statement of Minimum Operations to Make Elements Within K Subarrays Equal

You are given an integer array nums and two integers, x and k. You can perform the following operation any number of times (including zero):

Increase or decrease any element of nums by 1.

Return the minimum number of operations needed to have at least k non-overlapping subarrays of size exactly x in nums, where all elements within each subarray are equal.

Example 1:

Input: nums = [5,-2,1,3,7,3,6,4,-1], x = 3, k = 2
Output: 8
Explanation:

Use 3 operations to add 3 to nums[1] and use 2 operations to subtract 2 from nums[3]. The resulting array is [5, 1, 1, 1, 7, 3, 6, 4, -1].
Use 1 operation to add 1 to nums[5] and use 2 operations to subtract 2 from nums[6]. The resulting array is [5, 1, 1, 1, 7, 4, 4, 4, -1].
Now, all elements within each subarray [1, 1, 1] (from indices 1 to 3) and [4, 4, 4] (from indices 5 to 7) are equal. Since 8 total operations were used, 8 is the output.

Example 2:

Input: nums = [9,-2,-2,-2,1,5], x = 2, k = 2
Output: 3
Explanation:

Use 3 operations to subtract 3 from nums[4]. The resulting array is [9, -2, -2, -2, -2, 5].
Now, all elements within each subarray [-2, -2] (from indices 1 to 2) and [-2, -2] (from indices 3 to 4) are equal. Since 3 operations were used, 3 is the output.

Constraints:

2 <= nums.length <= 105
-106 <= nums[i] <= 106
2 <= x <= nums.length
1 <= k <= 15
2 <= k * x <= nums.length

Complexity Analysis

• Time Complexity: O(nk)
• Space Complexity: O(nk)

3505. Minimum Operations to Make Elements Within K Subarrays Equal LeetCode Solution in C++

class Solution {
 public:
  long long minOperations(vector<int>& nums, int x, int k) {
    // minOps[i] := the minimum number of operations needed to make
    // nums[i..i + x - 1] equal to the median
    const vector<long> minOps = getMinOps(nums, x);
    vector<vector<long>> mem(nums.size() + 1, vector<long>(k + 1, -1));
    return minOperations(nums, x, 0, k, minOps, mem);
  }

 private:
  static constexpr long kInf = LONG_MAX / 2;

  // Returns the minimum operations needed to have at least k non-overlapping
  // subarrays of size x in nums[i..n - 1].
  long minOperations(const vector<int>& nums, int x, int i, int k,
                     const vector<long>& minOps, vector<vector<long>>& mem) {
    if (k == 0)
      return 0;
    if (i == nums.size())
      return kInf;
    if (mem[i][k] != -1)
      return mem[i][k];
    const long skip = minOperations(nums, x, i + 1, k, minOps, mem);
    const long pick =
        i + x <= nums.size()
            ? minOps[i] + minOperations(nums, x, i + x, k - 1, minOps, mem)
            : kInf;
    return mem[i][k] = min(skip, pick);
  }

  // Returns the minimum operations needed to make all elements in the window of
  // size x equal to the median.
  vector<long> getMinOps(const vector<int>& nums, int x) {
    vector<long> minOps;
    multiset<int> lower;
    multiset<int> upper;
    long lowerSum = 0;
    long upperSum = 0;
    for (int i = 0; i < nums.size(); ++i) {
      if (lower.empty() || nums[i] <= *lower.rbegin()) {
        lower.insert(nums[i]);
        lowerSum += nums[i];
      } else {
        upper.insert(nums[i]);
        upperSum += nums[i];
      }
      if (i >= x) {
        const int outNum = nums[i - x];
        if (const auto it = lower.find(outNum); it != lower.cend()) {
          lower.erase(it);
          lowerSum -= outNum;
        } else {
          upper.erase(upper.find(outNum));
          upperSum -= outNum;
        }
      }
      // Balance the two multisets s.t.
      // |lower| >= |upper| and |lower| - |upper| <= 1.
      if (lower.size() < upper.size()) {
        const int val = *upper.begin();
        upper.erase(upper.begin());
        lower.insert(val);
        lowerSum += val;
        upperSum -= val;
      } else if (lower.size() - upper.size() > 1) {
        const int val = *lower.rbegin();
        lower.erase(prev(lower.end()));
        upper.insert(val);
        upperSum += val;
        lowerSum -= val;
      }
      // Calculate operations needed to make all elements in the window equal
      // to the median.
      if (i >= x - 1) {
        const int median = *lower.rbegin();
        const long ops = (median * lower.size() - lowerSum) +
                         (upperSum - median * upper.size());
        minOps.push_back(ops);
      }
    }
    return minOps;
  }
};
/* code provided by PROGIEZ */

3505. Minimum Operations to Make Elements Within K Subarrays Equal LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3505. Minimum Operations to Make Elements Within K Subarrays Equal LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.