# Minimum Operations to Make Array Equal to Target
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-operations-to-make-array-equal-to-target)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-array-equal-to-target
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack, Monotonic Stack
---
## 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`.

**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`

# Approaches
## Multi-Pass Approach with Auxiliary Arrays
This approach first simplifies the problem by calculating the difference between the target and the initial array. An operation of incrementing or decrementing a subarray in `nums` corresponds to decrementing or incrementing a subarray in the `diff` array, respectively. The core idea is that operations required to resolve positive differences are independent of those for negative differences. We can thus solve the problem for positive and negative differences separately and sum the results. This is done by creating two new arrays, one for positive differences (`pos`) and one for the absolute values of negative differences (`neg`), and then calculating the minimum operations for each, which is akin to solving a skyline problem.
**Time:** O(N), where N is the length of the arrays. It takes O(N) to create the `diff` array, O(N) to create `pos` and `neg` arrays, and O(N) for each of the two passes to calculate operations. This sums up to O(N). · **Space:** O(N), where N is the length of the arrays. We use three auxiliary arrays (`diff`, `pos`, `neg`), each of size N.
**Pros:** Conceptually clear and easy to follow.; Separates the problem into two simpler, independent subproblems.
**Cons:** Requires O(N) extra space for three auxiliary arrays.; Less efficient due to multiple passes over the data.; Can be simplified into a single-pass algorithm.
### Explanation
The problem can be rephrased as: what is the minimum number of operations to make an array `diff` (where `diff[i] = target[i] - nums[i]`) all zeros, by adding or subtracting 1 from its subarrays.

Operations that add to `diff` (decrementing `nums`) only help with negative `diff` values. Operations that subtract from `diff` (incrementing `nums`) only help with positive `diff` values. Thus, the two problems are decoupled.

1.  **Create `diff`, `pos`, and `neg` arrays**: We first compute `diff[i] = target[i] - nums[i]`. Then, we separate the positive and negative parts into two arrays: `pos[i] = max(0, diff[i])` and `neg[i] = max(0, -diff[i])`.

2.  **Calculate Operations for `pos` array**: The problem of making the `pos` array zero by subtracting 1 from subarrays is equivalent to finding the minimum number of horizontal strips to cover a skyline. The number of operations is the sum of all new upward steps. We can calculate this by iterating through the `pos` array and adding `pos[i] - pos[i-1]` whenever `pos[i] > pos[i-1]`.

3.  **Calculate Operations for `neg` array**: We do the same for the `neg` array.

4.  **Sum the results**: The total minimum operations is the sum of operations for the `pos` and `neg` parts.

```java
class Solution {
    public long minimumOperations(int[] nums, int[] target) {
        int n = nums.length;
        long[] diff = new long[n];
        for (int i = 0; i < n; i++) {
            diff[i] = (long)target[i] - nums[i];
        }

        long[] pos = new long[n];
        long[] neg = new long[n];
        for (int i = 0; i < n; i++) {
            if (diff[i] > 0) {
                pos[i] = diff[i];
            } else {
                neg[i] = -diff[i];
            }
        }

        long positiveOps = 0;
        long prevPos = 0;
        for (long p : pos) {
            if (p > prevPos) {
                positiveOps += p - prevPos;
            }
            prevPos = p;
        }

        long negativeOps = 0;
        long prevNeg = 0;
        for (long negVal : neg) {
            if (negVal > prevNeg) {
                negativeOps += negVal - prevNeg;
            }
            prevNeg = negVal;
        }

        return positiveOps + negativeOps;
    }
}
```
### Algorithm
- Create a `diff` array of size `n` where `diff[i] = target[i] - nums[i]`.
- Create a `pos` array of size `n` where `pos[i] = max(0, diff[i])`.
- Create a `neg` array of size `n` where `neg[i] = max(0, -diff[i])`.
- Initialize `total_ops = 0`.
- Calculate operations for the positive part:
  - Initialize `positive_ops = 0` and `prev_pos = 0`.
  - Iterate through the `pos` array. For each element `p`, add `max(0, p - prev_pos)` to `positive_ops`. Update `prev_pos = p`.
- Calculate operations for the negative part:
  - Initialize `negative_ops = 0` and `prev_neg = 0`.
  - Iterate through the `neg` array. For each element `n`, add `max(0, n - prev_neg)` to `negative_ops`. Update `prev_neg = n`.
- The result is `positive_ops + negative_ops`.

## Single-Pass over an Auxiliary Array
This approach improves upon the first one by combining the multiple passes into a single pass. After computing the `diff` array, we can calculate the total operations in one iteration. In this single pass, we keep track of the previous positive requirement and the previous negative requirement. At each element, we calculate the new operations needed by comparing the current positive/negative requirements with the previous ones. This avoids creating separate `pos` and `neg` arrays and processing them independently.
**Time:** O(N), as it involves one pass to create the `diff` array and one pass to compute the operations. · **Space:** O(N), for storing the `diff` array.
**Pros:** More efficient than the multi-pass approach as it combines computation into a single loop.; The logic is a direct implementation of the skyline covering problem for both positive and negative parts.
**Cons:** Still requires O(N) extra space for the difference array.
### Explanation
Building on the insight that positive and negative differences can be handled separately, we can optimize the process to a single pass over the `diff` array. Instead of creating explicit `pos` and `neg` arrays, we can compute the required operations on the fly.

We iterate through the `diff` array, maintaining two variables: `prev_pos` (the positive difference at the previous index) and `prev_neg` (the absolute negative difference at the previous index). For each element `diff[i]`:

- We find the `current_pos = max(0, diff[i])` and `current_neg = max(0, -diff[i])`.
- If `current_pos > prev_pos`, it means we have an upward step in the positive skyline, requiring `current_pos - prev_pos` new increment operations on `nums`. We add this to our total.
- Similarly, if `current_neg > prev_neg`, it signifies an upward step in the negative skyline (in terms of magnitude), requiring `current_neg - prev_neg` new decrement operations on `nums`.
- After processing the element, we update `prev_pos` and `prev_neg` for the next iteration.

This method correctly accumulates all required operations in a single, efficient pass.

```java
class Solution {
    public long minimumOperations(int[] nums, int[] target) {
        int n = nums.length;
        long[] diff = new long[n];
        for (int i = 0; i < n; i++) {
            diff[i] = (long)target[i] - nums[i];
        }

        long totalOps = 0;
        long prevPos = 0;
        long prevNeg = 0;

        for (long d : diff) {
            long currentPos = Math.max(0, d);
            long currentNeg = Math.max(0, -d);

            totalOps += Math.max(0, currentPos - prevPos);
            totalOps += Math.max(0, currentNeg - prevNeg);

            prevPos = currentPos;
            prevNeg = currentNeg;
        }

        return totalOps;
    }
}
```
### Algorithm
- Create a `diff` array of size `n` where `diff[i] = target[i] - nums[i]`.
- Initialize `total_ops = 0`, `prev_pos = 0`, and `prev_neg = 0`.
- Iterate through the `diff` array from `i = 0` to `n-1`:
  - Let `d = diff[i]`.
  - Determine the current positive and negative requirements: `current_pos = max(0, d)` and `current_neg = max(0, -d)`.
  - Add the new operations required at this step: `total_ops += max(0, current_pos - prev_pos)` and `total_ops += max(0, current_neg - prev_neg)`.
  - Update the previous state: `prev_pos = current_pos` and `prev_neg = current_neg`.
- Return `total_ops`.

## Single-Pass with Constant Space
This is the most efficient approach, optimizing the previous method to use constant extra space. We realize that to calculate the operations needed at index `i`, we only need the difference at `i` and the difference at `i-1`. Therefore, storing the entire `diff` array is unnecessary. We can iterate through the input arrays `nums` and `target` once, calculating the difference at each index on the fly. We maintain the state of the previous positive and negative requirements and update the total operations in a single pass, achieving optimal time and space complexity.
**Time:** O(N), where N is the length of the arrays. We perform a single pass through the input arrays. · **Space:** O(1), as we only use a few variables to store the state of the previous step, regardless of the input size.
**Pros:** Optimal space complexity of O(1).; Optimal time complexity of O(N) with a single pass.; Highly efficient for very large inputs.
**Cons:** The combined logic might be slightly less immediately obvious than separating the problem into explicit steps.
### Explanation
This approach refines the single-pass logic to eliminate the need for any auxiliary arrays, thus reducing the space complexity to O(1).

The core logic remains identical to the previous approach. The key observation is that at each step `i` of the iteration, the calculation only depends on the difference at `i` and the state (`prev_pos`, `prev_neg`) from step `i-1`. We never need to look further back.

So, instead of pre-computing and storing all differences in a `diff` array, we can compute `d = target[i] - nums[i]` inside the loop. The rest of the logic for updating `totalOps`, `prev_pos`, and `prev_neg` is the same. This avoids the O(N) space overhead of the `diff` array, making the solution highly efficient for large inputs.

```java
class Solution {
    public long minimumOperations(int[] nums, int[] target) {
        int n = nums.length;
        long totalOps = 0;
        long prevPos = 0;
        long prevNeg = 0;

        for (int i = 0; i < n; i++) {
            long d = (long)target[i] - nums[i];
            long currentPos = 0;
            long currentNeg = 0;

            if (d > 0) {
                currentPos = d;
            } else {
                currentNeg = -d;
            }

            // Add operations for new positive requirements
            if (currentPos > prevPos) {
                totalOps += currentPos - prevPos;
            }

            // Add operations for new negative requirements
            if (currentNeg > prevNeg) {
                totalOps += currentNeg - prevNeg;
            }

            prevPos = currentPos;
            prevNeg = currentNeg;
        }

        return totalOps;
    }
}
```
### Algorithm
- Initialize `total_ops = 0`, `prev_pos = 0`, and `prev_neg = 0`.
- Iterate from `i = 0` to `n-1`:
  - Calculate the current difference on the fly: `d = target[i] - nums[i]`.
  - Determine the current positive and negative requirements: `current_pos = max(0, d)` and `current_neg = max(0, -d)`.
  - Add the new operations required: `total_ops += max(0, current_pos - prev_pos)` and `total_ops += max(0, current_neg - prev_neg)`.
  - Update the state for the next iteration: `prev_pos = current_pos` and `prev_neg = current_neg`.
- Return `total_ops`.

# Solutions
### Java

```java
class Solution {
public
  long minimumOperations(int[] nums, int[] target) {
    long f = Math.abs(target[0] - nums[0]);
    for (int i = 1; i < nums.length; ++i) {
      long x = target[i] - nums[i];
      long y = target[i - 1] - nums[i - 1];
      if (x * y > 0) {
        long d = Math.abs(x) - Math.abs(y);
        if (d > 0) {
          f += d;
        }
      } else {
        f += Math.abs(x);
      }
    }
    return f;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumOperations(vector<int> &nums, vector<int> &target) {
    using ll = long long;
    ll f = abs(target[0] - nums[0]);
    for (int i = 1; i < nums.size(); ++i) {
      long x = target[i] - nums[i];
      long y = target[i - 1] - nums[i - 1];
      if (x * y > 0) {
        ll d = abs(x) - abs(y);
        if (d > 0) {
          f += d;
        }
      } else {
        f += abs(x);
      }
    }
    return f;
  }
};

```

### Python

```python
class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int: n = len(nums) f = abs(target[0] - nums[0]) for i in range(1, n): x = target[i] - nums[i] y = target[i - 1] - nums[i - 1] if x * y > 0: d = abs(x) - abs(y) if d > 0: f += d else: f += abs(x) return f

```