Minimum Operations to Make Array Equal to Target
HardPrompt
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 <= 1051 <= nums[i], target[i] <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a
diffarray of sizenwherediff[i] = target[i] - nums[i]. - Create a
posarray of sizenwherepos[i] = max(0, diff[i]). - Create a
negarray of sizenwhereneg[i] = max(0, -diff[i]). - Initialize
total_ops = 0. - Calculate operations for the positive part:
- Initialize
positive_ops = 0andprev_pos = 0. - Iterate through the
posarray. For each elementp, addmax(0, p - prev_pos)topositive_ops. Updateprev_pos = p.
- Initialize
- Calculate operations for the negative part:
- Initialize
negative_ops = 0andprev_neg = 0. - Iterate through the
negarray. For each elementn, addmax(0, n - prev_neg)tonegative_ops. Updateprev_neg = n.
- Initialize
- The result is
positive_ops + negative_ops.
Walkthrough
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.
-
Create
diff,pos, andnegarrays: We first computediff[i] = target[i] - nums[i]. Then, we separate the positive and negative parts into two arrays:pos[i] = max(0, diff[i])andneg[i] = max(0, -diff[i]). -
Calculate Operations for
posarray: The problem of making theposarray 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 theposarray and addingpos[i] - pos[i-1]wheneverpos[i] > pos[i-1]. -
Calculate Operations for
negarray: We do the same for thenegarray. -
Sum the results: The total minimum operations is the sum of operations for the
posandnegparts.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a
diffarray of sizenwherediff[i] = target[i] - nums[i]. - Initialize
total_ops = 0,prev_pos = 0, andprev_neg = 0. - Iterate through the
diffarray fromi = 0ton-1:- Let
d = diff[i]. - Determine the current positive and negative requirements:
current_pos = max(0, d)andcurrent_neg = max(0, -d). - Add the new operations required at this step:
total_ops += max(0, current_pos - prev_pos)andtotal_ops += max(0, current_neg - prev_neg). - Update the previous state:
prev_pos = current_posandprev_neg = current_neg.
- Let
- Return
total_ops.
Walkthrough
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])andcurrent_neg = max(0, -diff[i]). - If
current_pos > prev_pos, it means we have an upward step in the positive skyline, requiringcurrent_pos - prev_posnew increment operations onnums. 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), requiringcurrent_neg - prev_negnew decrement operations onnums. - After processing the element, we update
prev_posandprev_negfor the next iteration.
This method correctly accumulates all required operations in a single, efficient pass.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
total_ops = 0,prev_pos = 0, andprev_neg = 0. - Iterate from
i = 0ton-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)andcurrent_neg = max(0, -d). - Add the new operations required:
total_ops += max(0, current_pos - prev_pos)andtotal_ops += max(0, current_neg - prev_neg). - Update the state for the next iteration:
prev_pos = current_posandprev_neg = current_neg.
- Calculate the current difference on the fly:
- Return
total_ops.
Walkthrough
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.
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; }}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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 fVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.