Minimum Operations to Make Array Equal to Target - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Approach 1: Calculate Total Difference
In this approach, we calculate the difference between each element in the 'nums' array and the 'target' array. We then sum the absolute values of these differences. This sum represents the total number of operations required to make the 'nums' array equal to the 'target' array.
This Python solution utilizes the zip function to iterate over pairs of elements from 'nums' and 'target'. It computes the absolute difference for each pair and sums these values to find the minimum number of operations required.
Complexity
Time Complexity: O(n), where n is the length of the 'nums' array, as we iterate through the array once.
Space Complexity: O(1), as we use a constant amount of extra space.
Approach 2: Approach 2: Increment or Decrement Step-wise
This approach involves incrementing or decrementing each element in 'nums' step-wise towards the corresponding value in 'target'. It iteratively adjusts each element to minimize operations.
This Python implementation directly loops through the elements of arrays 'nums' and 'target'. It adjusts each element of the 'nums' array to match the 'target' array using increment or decrement operations performed step-wise.
Complexity
Time Complexity: O(n + k), where n is the array length and k is the total number of operations.
Space Complexity: O(1), as the space used is constant.
Approach 3: Dynamic Programming
We can first calculate the difference between the arrays nums and target. For a difference array, we find continuous intervals where the signs of the differences are the same. For each interval, we add the absolute value of the first element to the result. For the subsequent elements, if the absolute value of the difference is greater than the absolute value of the previous difference, we add the difference of the absolute values to the result.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Calculate Total Difference | Time Complexity: O(n), where n is the length of the 'nums' array, as we iterate through the array once. |
| Approach 2: Increment or Decrement Step-wise | Time Complexity: O(n + k), where n is the array length and k is the total number of operations. |
| Dynamic Programming | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Minimum Operations to Make Array Equal to Target | Minimum Number of Increments|Leetcode 3229 & 1526 • codestorywithMIK • 13,853 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Minimum Operations to Make Array Equal to Target easy or hard?
Minimum Operations to Make Array Equal to Target Python/Java solution
How to solve Minimum Operations to Make Array Equal to Target in O(n)?
What is the best approach for Minimum Operations to Make Array Equal to Target?
Is Minimum Operations to Make Array Equal to Target asked at Google/Amazon/Meta?
What data structure is used in Minimum Operations to Make Array Equal to Target?
What is the time complexity of Minimum Operations to Make Array Equal to Target?
Ready to solve this problem?
Practice Minimum Operations to Make Array Equal to Target with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor