Minimum Operations to Make Array Equal to Target

hard monotonic stack greedy difference array

Problem

Given two positive integer arrays nums and target of equal length, one operation lets you pick any subarray of nums and add 1 to every element of it, or subtract 1 from every element of it. Return the minimum number of operations needed to make nums equal to target.

Work on the difference array d[i] = target[i] − nums[i]; the goal becomes turning every d[i] into 0. Picture d as a signed staircase: each step either climbs higher, descends, or flips sign, and the cost is the total of all the new height a range operation must create.

Inputnums = [3,5,1,2], target = [4,6,2,4]

Output2

d = [1,1,1,2]. Increment nums[0..3] by 1, then nums[3..3] by 1. Two operations.

nums (comma-separated)

target (comma-separated)

def minimumOperations(nums, target):
    n = len(nums)
    # d[i] = how much element i must rise (+) or fall (-)
    d = [target[i] - nums[i] for i in range(n)]
    # First column always needs |d[0]| fresh operations.
    ops = abs(d[0])
    for i in range(1, n):
        prev, cur = d[i - 1], d[i]
        if prev >= 0 and cur >= 0:
            # same sign (up): only the extra climb is new work
            ops += max(0, cur - prev)
        elif prev <= 0 and cur <= 0:
            # same sign (down): only the extra descent is new
            ops += max(0, prev - cur)
        else:
            # signs differ: previous layers cannot be reused
            ops += abs(cur)
    return ops

function minimumOperations(nums, target) {
  const n = nums.length;
  // d[i] = how much element i must rise (+) or fall (-)
  const d = nums.map((v, i) => target[i] - v);
  // First column always needs |d[0]| fresh operations.
  let ops = Math.abs(d[0]);
  for (let i = 1; i < n; i++) {
    const prev = d[i - 1], cur = d[i];
    if (prev >= 0 && cur >= 0) {
      // same sign (up): only the extra climb is new work
      ops += Math.max(0, cur - prev);
    } else if (prev <= 0 && cur <= 0) {
      // same sign (down): only the extra descent is new
      ops += Math.max(0, prev - cur);
    } else {
      // signs differ: previous layers cannot be reused
      ops += Math.abs(cur);
    }
  }
  return ops;
}

long minimumOperations(int[] nums, int[] target) {
    int n = nums.length;
    // d[i] = how much element i must rise (+) or fall (-)
    long[] d = new long[n];
    for (int i = 0; i < n; i++) d[i] = target[i] - nums[i];
    // First column always needs |d[0]| fresh operations.
    long ops = Math.abs(d[0]);
    for (int i = 1; i < n; i++) {
        long prev = d[i - 1], cur = d[i];
        if (prev >= 0 && cur >= 0) {
            // same sign (up): only the extra climb is new work
            ops += Math.max(0, cur - prev);
        } else if (prev <= 0 && cur <= 0) {
            // same sign (down): only the extra descent is new
            ops += Math.max(0, prev - cur);
        } else {
            // signs differ: previous layers cannot be reused
            ops += Math.abs(cur);
        }
    }
    return ops;
}

long long minimumOperations(vector<int>& nums, vector<int>& target) {
    int n = nums.size();
    // d[i] = how much element i must rise (+) or fall (-)
    vector<long long> d(n);
    for (int i = 0; i < n; i++) d[i] = (long long)target[i] - nums[i];
    // First column always needs |d[0]| fresh operations.
    long long ops = llabs(d[0]);
    for (int i = 1; i < n; i++) {
        long long prev = d[i - 1], cur = d[i];
        if (prev >= 0 && cur >= 0) {
            // same sign (up): only the extra climb is new work
            ops += max(0LL, cur - prev);
        } else if (prev <= 0 && cur <= 0) {
            // same sign (down): only the extra descent is new
            ops += max(0LL, prev - cur);
        } else {
            // signs differ: previous layers cannot be reused
            ops += llabs(cur);
        }
    }
    return ops;
}

Explanation

Subtracting nums from target gives a difference array d, and the task reduces to flattening d to all zeros using range +1 / −1 operations. A single operation paints a contiguous block by one unit, so think of building d as a stack of horizontal layers laid down over consecutive columns.

Read the array left to right and treat it like a monotonic stack of layers. Positive values are layers above the baseline; negative values are layers below it. When you move from column i-1 to column i, every layer that is already in place can be extended for free into the new column — that costs no extra operation. You only pay for the layers you must newly start.

That gives a clean rule. If prev and cur share a sign and you go further from zero, you pay the gap |cur| - |prev|; if you come back toward zero, the surplus layers simply end here at no cost, so you pay nothing. If the signs differ, none of the old layers can carry over (they were on the opposite side of the baseline), so you must open |cur| brand-new layers.

The very first column has nothing to its left, so it always costs |d[0]|. Summing the new layers across the whole scan yields the minimum number of operations — exactly the total height the staircase ever rises as you walk it, measured separately above and below the line.

Example: nums = [3,5,1,2], target = [4,6,2,4] give d = [1,1,1,2]. Pay 1 for the first column, 0 across the flat 1→1→1 stretch, then 1 for the climb 1→2. Total = 2 operations.

Time: O(n) Space: O(n)