Watch 9 video solutions for Minimum Operations to Make Array Equal to Target, a hard level problem involving Array, Dynamic Programming, Stack. This walkthrough by codestorywithMIK has 13,107 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 108Problem Overview: You are given two arrays nums and target. One operation increments or decrements every element in a chosen subarray by 1. The goal is to transform nums into target using the minimum number of operations.
Approach 1: Calculate Total Difference (Greedy) (Time: O(n), Space: O(1))
The key idea is to work with a difference array: diff[i] = target[i] - nums[i]. Each operation effectively increases or decreases a contiguous segment of diff by 1. Instead of simulating operations, track how much additional adjustment is required compared to the previous index. If diff[i] is greater than diff[i-1], you must start new increment operations equal to that increase. If it decreases, existing operations naturally end. The total operations equal the sum of all positive increases across the array. This greedy observation converts the problem into a single pass calculation.
This works because a subarray operation can extend forward as long as the required difference does not shrink. Once the required adjustment drops, the previous operations must stop. The method resembles processing height changes in a skyline and is closely related to patterns used in array difference problems and greedy prefix adjustments.
Approach 2: Increment or Decrement Step-wise (Segment Expansion) (Time: O(n), Space: O(1))
Another way to reason about the problem is to explicitly track how many active increment or decrement operations are currently affecting the index. Compute diff[i], then gradually extend operations across the array while the required difference continues in the same direction. When the required difference grows, start additional operations; when it shrinks, some operations terminate. This mirrors maintaining monotonic segments of required adjustments.
The logic is conceptually similar to maintaining levels with a monotonic stack or tracking transitions between increasing and decreasing requirements. Although implemented with simple variables, the idea resembles techniques from dynamic programming where the current state depends on the previous adjustment level.
Recommended for interviews: The greedy difference approach is the expected solution. Interviewers want to see that you convert the transformation into a difference array and count only the positive increases between adjacent elements. A brute simulation shows understanding of the operation, but the O(n) greedy insight demonstrates strong problem‑solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Calculate Total Difference (Greedy) | O(n) | O(1) | Best general solution. Single pass using difference array and counting positive increases. |
| Increment or Decrement Step-wise | O(n) | O(1) | Useful for understanding how operations expand across segments and why the greedy method works. |