3229. Minimum Operations to Make Array Equal to Target

Description

You are given two positive integer arrays nums and target, both 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. Your task is to return the minimum number of operations required to make nums equal to the array target.

Intuition

The main challenge is to align the values of nums with target using the fewest operations. By focusing on the differences between corresponding elements in nums and target, we can devise a strategy to efficiently achieve this alignment.

Approach

1. Calculate Differences: Compute the difference between each corresponding element of nums and target.
2. Track Positive and Negative Differences: Use two variables, incr and decr, to track ongoing positive and negative adjustments needed as you iterate through the differences.
3. Count Operations: For each difference: - If the difference is positive and greater than incr, increment the operation count by the surplus needed to adjust. - If the difference is negative and its absolute value is greater than decr, increment the operation count by the surplus needed to adjust. - Adjust the incr and decr counters accordingly.
4. Reset Counters for Equal Values: When the difference is zero, reset both counters.
5. Return the Total Operations: The total operations tracked provide the minimum number required to make nums equal to target.

Complexity

• Time Complexity: O(n), where n is the length of the arrays. This is because we iterate through the arrays once.
• Space Complexity: O(1), as we use a fixed amount of space for the counters regardless of the input size.

Code

C++

class Solution {
public:
    long long minimumOperations(vector& nums, vector& target) {
        long long inc = 0, dec = 0, res = 0;

        for (int i = 0; i < nums.size(); ++i) {
            int d = target[i] - nums[i];

            if (d > 0) {
                if (inc < d) res += d - inc;
                inc = d;
                dec = 0;
            } else if (d < 0) {
                if (dec < -d) res += -d - dec;
                dec = -d;
                inc = 0;
            } else {
                inc = 0;
                dec = 0;
            }
        }

        return res;
    }
};

Python

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        inc = 0
        dec = 0
        res = 0

        for i in range(len(nums)):
            d = target[i] - nums[i]

            if d > 0:
                if inc < d:
                    res += d - inc
                inc = d
                dec = 0
            elif d < 0:
                if dec < -d:
                    res += -d - dec
                dec = -d
                inc = 0
            else:
                inc = 0
                dec = 0

        return res

Java

class Solution {
    public long minimumOperations(int[] nums, int[] target) {
        long inc = 0, dec = 0, res = 0;

        for (int i = 0; i < nums.length; i++) {
            int d = target[i] - nums[i];

            if (d > 0) {
                if (inc < d) res += d - inc;
                inc = d;
                dec = 0;
            } else if (d < 0) {
                if (dec < -d) res += -d - dec;
                dec = -d;
                inc = 0;
            } else {
                inc = 0;
                dec = 0;
            }
        }

        return res;
    }
}

JavaScript

var minimumOperations = function (nums, target) {
    var inc = 0, dec = 0, res = 0;

    for (var i = 0; i < nums.length; i++) {
        var d = target[i] - nums[i];

        if (d > 0) {
            if (inc < d) res += d - inc;
            inc = d;
            dec = 0;
        } else if (d < 0) {
            if (dec < -d) res += -d - dec;
            dec = -d;
            inc = 0;
        } else inc = dec = 0;
    }

    return res;
};