3229-minimum-operations-to-make-array-equal-to-target

Try it on leetcode

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 each element within that subarray by 1 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:

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:
- Increment nums[0..3] by 1, nums = [4,6,2,3].
- Increment nums[3..3] by 1, nums = [4,6,2,4].

Example 2:

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

Output: 5

Explanation:

We will perform the following operations to make nums equal to target:
- Increment nums[0..0] by 1, nums = [2,3,2].
- Decrement nums[1..1] by 1, nums = [2,2,2].
- Decrement nums[1..1] by 1, nums = [2,1,2].
- Increment nums[2..2] by 1, nums = [2,1,3].
- Increment nums[2..2] by 1, nums = [2,1,4].

 

Constraints:

• 1 <= nums.length == target.length <= 105
• 1 <= nums[i], target[i] <= 108

Solution(Python)

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
                # length of array
        n = len(nums)

        # calculate difference array 
        # includes +ve and -ve values
        diff = [target[i] - nums[i] for i in range(n)]

        # the initial difference has to fully contribute to operations.
        min_ops = abs(diff[0])

        # loop through rest of the array
        for i in range(1, n):

            # if both differences are positive,
            if diff[i-1] >= 0 and diff[i] >= 0:

                # the subsequent difference will only add operations if it is
                # bigger than the previous difference
                min_ops += max(diff[i] - diff[i - 1], 0)
            
            # if both differences are negative,
            elif diff[i-1] <= 0 and diff[i] <= 0:
                # the subsequent difference will only add operations if it is
                # more negative than the previous difference
                min_ops += max(abs(diff[i]) - abs(diff[i - 1]), 0)
            
            # if both differences are opposite parity,
            else:
                # the difference contributes fully to operations
                min_ops += abs(diff[i])
        
        return min_ops