Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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 <= 10^5
  • 1 <= nums[i], target[i] <= 10^8

Solution

Method 1 – Greedy & Difference Array

Intuition

The only thing that matters is the difference between nums[i] and target[i] at each position. Since we can increment or decrement any subarray, the minimum number of operations is the sum of absolute changes between consecutive positions in the difference array.

Approach

  1. Compute the difference array: diff[i] = nums[i] - target[i].
  2. The minimum number of operations is the sum of absolute values of diff[i] - diff[i-1] for i from 1 to n-1, plus abs(diff[0]).
  3. This works because each operation can adjust a contiguous segment, so only changes in the difference matter.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& target) {
        int n = nums.size(), ans = abs(nums[0] - target[0]);
        for (int i = 1; i < n; ++i) {
            ans += abs((nums[i] - target[i]) - (nums[i-1] - target[i-1]));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func minOperations(nums []int, target []int) int {
    n := len(nums)
    ans := abs(nums[0] - target[0])
    for i := 1; i < n; i++ {
        ans += abs((nums[i] - target[i]) - (nums[i-1] - target[i-1]))
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int minOperations(int[] nums, int[] target) {
        int n = nums.length, ans = Math.abs(nums[0] - target[0]);
        for (int i = 1; i < n; ++i) {
            ans += Math.abs((nums[i] - target[i]) - (nums[i-1] - target[i-1]));
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun minOperations(nums: IntArray, target: IntArray): Int {
        var ans = kotlin.math.abs(nums[0] - target[0])
        for (i in 1 until nums.size) {
            ans += kotlin.math.abs((nums[i] - target[i]) - (nums[i-1] - target[i-1]))
        }
        return ans
    }
}
1
2
3
4
5
6

class Solution:
    def minOperations(self, nums: list[int], target: list[int]) -> int:
        ans: int = abs(nums[0] - target[0])
        for i in range(1, len(nums)):
            ans += abs((nums[i] - target[i]) - (nums[i-1] - target[i-1]))
        return ans
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn min_operations(nums: Vec<i32>, target: Vec<i32>) -> i32 {
        let mut ans = (nums[0] - target[0]).abs();
        for i in 1..nums.len() {
            ans += ((nums[i] - target[i]) - (nums[i-1] - target[i-1])).abs();
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    minOperations(nums: number[], target: number[]): number {
        let ans = Math.abs(nums[0] - target[0]);
        for (let i = 1; i < nums.length; ++i) {
            ans += Math.abs((nums[i] - target[i]) - (nums[i-1] - target[i-1]));
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the arrays once, computing differences and summing.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.