We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make Array Equal to Target

Number: 3454

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given two positive integer arrays nums and target of equal length, you may in one operation choose any contiguous subarray of nums and either increment every element in that subarray by 1 or decrement every element in that subarray by 1. The goal is to make nums become exactly equal to target by performing the minimum number of operations.

Key Insights

  • Define for each index i the difference diff[i] = target[i] – nums[i]. Positive values of diff mean we must “raise” nums[i] (by applying increment‐operations) and negative values mean we must “lower” nums[i] (by applying decrement–operations).
  • Because an operation adds/subtracts 1 to a contiguous block, if consecutive indices need an adjustment of the same sign, many of their changes may be “done together.”
  • The key is to “break” the diff array into segments where the sign does not change. Then for each segment the minimum additional operations is the extra “amount” needed when the required adjustment increases (if positive) or becomes more negative (if negative) as you go from one index to the next.
  • More precisely, initialize the answer with |diff[0]|. Then for every subsequent index i:
    • If diff[i] is zero or the “direction” (sign) of diff[i] differs from that of diff[i–1] then no opportunity to “re-use” previous operations exists and we add |diff[i]|.
    • Otherwise (the two consecutive differences have the same sign) only the extra difference beyond diff[i–1] must be fixed. For positives, add max(0, diff[i] – diff[i–1]); for negatives add max(0, diff[i–1] – diff[i]).

For example, in the first sample diff = [1,1,1,2] (all positive). We start with 1 op then add (2–1)=1 op to fix the jump at the end (total 2 ops). In the second sample diff = [1, –2, 2] the sign changes force us to “restart” the covering operation on that index so that the op‐cost becomes 1 + 2 + 2 = 5.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the arrays (we make a single pass through diff).
Space Complexity: O(n) if we store the diff array explicitly; it can be O(1) extra space if computed on the fly.

Solution

We first compute the difference array diff such that diff[i] = target[i] – nums[i]. Conceptually, this represents how many times (and in which direction) index i must be “operated on.” Operations are “contiguous‐range” additions or subtractions. If two consecutive indices require adjustments in the same direction (both positive or both negative), then an operation on a contiguous segment can cover both. However, if the sign changes – or if one index needs no change – the operations cannot be “blended” and we must fix that index (or segment) independently. Thus, we initialize our answer to |diff[0]| (the “cost” for the first index). Then for each subsequent index from 1 to n–1, we check: • If diff[i] is zero or its sign differs from diff[i–1] then we add |diff[i]| since the adjustment “starts over.” • If diff[i] and diff[i–1] have the same sign then only an increase in adjustment is extra work:  – For positive diff, if diff[i] > diff[i–1] then add (diff[i] – diff[i–1]).  – For negative diff, if diff[i] < diff[i–1] then add (diff[i–1] – diff[i]). This correctly “accounts” for saving operations when a previous contiguous subarray operation has already done part of the work. Some examples:  Example 1: nums = [3,5,1,2], target = [4,6,2,4] → diff = [1,1,1,2] gives operations = |1| + (max(0,1–1)) + (max(0,1–1)) + (max(0,2–1)) = 1 + 0 + 0 + 1 = 2.  Example 2: nums = [1,3,2], target = [2,1,4] → diff = [1, –2, 2] gives operations = |1| + |–2| (since sign change) + |2| (since sign change) = 1 + 2 + 2 = 5.

A slight gotcha is careful treatment of zeros. In our “if‐same–sign” check a zero or a change in sign is treated as a “restart” (simply add |diff[i]|).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line‐by‐line comments.

# Python solution
def minOperations(nums, target):
    n = len(nums)
    # Compute the initial difference for the 0th index.
    diff0 = target[0] - nums[0]
    ops = abs(diff0)
    prev = diff0
    # Process subsequent indices.
    for i in range(1, n):
        # Compute the required adjustment at index i.
        curr = target[i] - nums[i]
        # If current diff is zero or the sign changes compared to previous diff,
        # we need to perform all operations for curr separately.
        if prev == 0 or curr == 0 or (prev > 0 and curr < 0) or (prev < 0 and curr > 0):
            ops += abs(curr)
        else:
            # Same sign: if positive and current diff is larger than prev,
            # only the extra amount is needed.
            if curr > prev:
                ops += curr - prev
            # For negatives, if curr is even more negative than prev,
            # add the extra absolute difference.
            elif curr < prev:
                ops += prev - curr
        prev = curr
    return ops

# Example usage:
#print(minOperations([3,5,1,2], [4,6,2,4]))  # Output: 2
#print(minOperations([1,3,2], [2,1,4]))      # Output: 5
← Back to All Questions