3229. Minimum Operations to Make Array Equal to Target

Posted on Edited on In

3229. Minimum Operations to Make Array Equal to Target

Description

You are given two positive integer arrays nums and target, of the same length.

In a single operation, you can select any subarray of nums and increment or decrement each element within that subarray by 1.

Return the minimum number of operations required to make nums equal to the array target.

Example 1:

1
2
3
Input: nums = [3,5,1,2], target = [4,6,2,4]

Output: 2

Explanation:

We will perform the following operations to make nums equal to target:

  • Incrementnums[0..3] by 1, nums = [4,6,2,3].
  • Incrementnums[3..3] by 1, nums = [4,6,2,4].

Example 2:

1
2
3
Input: nums = [1,3,2], target = [2,1,4]

Output: 5

Explanation:

We will perform the following operations to make nums equal to target:

  • Incrementnums[0..0] by 1, nums = [2,3,2].
  • Decrementnums[1..1] by 1, nums = [2,2,2].
  • Decrementnums[1..1] by 1, nums = [2,1,2].
  • Incrementnums[2..2] by 1, nums = [2,1,3].
  • Incrementnums[2..2] by 1, nums = [2,1,4].

Constraints:

  • 1 <= nums.length == target.length <= 10^5
  • 1 <= nums[i], target[i] <= 10^8

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    long long minimumOperations(vector<int>& nums, vector<int>& target) {
        vector<int> gap;
        // first we get the gap array
        // from the question, it would be {1, 1, 1, 2}
        for (int i = 0; i < nums.size(); i++) {
            gap.push_back(target[i] - nums[i]);
        }
        // then, we get the diff array of the difference array
        // it would be {1, 0, 0, 1}
        vector<int> diff;
        diff.push_back(gap[0]);
        for (int i = 1; i < nums.size(); i++) {
            diff.push_back(gap[i] - gap[i - 1]);
        }
        int cur = 0;
        // the diff array's default effect is to the end of the array
        // but since we can apply the change to any subArray, we get free
        // add/minus from previous minus/add
        long long res = 0;
        for (int i = 0; i < diff.size(); i++) {
            if ((cur >= 0 && diff[i] >= 0) || (cur <= 0 && diff[i] <= 0)) {
                res += abs(diff[i]);
            } else {
                if (abs(cur) < abs(diff[i])) {
                    res += abs(diff[i] + cur);
                }
            }
            cur += diff[i];
        }
        return res;
    }
};