Minimum Operations to Make Array Equal to Target solution and explanation
Google
8 more videos on this problem
Minimum Operations to Make Array Equal to Target | Minimum Number of Increments|Leetcode 3229 & 1526codestorywithMIK · 45:23 · 13K views
3229. Minimum Operations to Make Array Equal to Target | Greedy | With ProofAryan Mittal · 24:51 · 6K views
A-D | Leetcode Weekly Contest 407 Editorials | Minimum Operations to Make Array Equal to TargetAbhinav Awasthi · 26:27 · 2K views
3229. Minimum Operations to Make Array Equal to Target | Weekly Leetcode 407codingMohan · 47:21 · 1K views
3229. Minimum Operations to Make Array Equal to Target (Leetcode Hard)Programming Live with Larry · 53:39 · 513 views
Leetcode | Weekly Contest 407 | D | 3229 | 3229. Minimum Operations to Make Array Equal to TargetPretest Passed · 14:34 · 486 views
Leetcode 3229. Minimum Operations to Make Array Equal to TargetEngineerCorner · 9:17 · 147 views
3229. Minimum Operations to Make Array Equal to Target | GreedyTech Courses · 18:06 · 122 views
Leetcode contest 407 | 3229 - Minimum Operations to Make Array Equal to Target #explainedinhindiBoraXAlgo · 8:10 · 77 views
The problem
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.
def min_operations(nums, target):
return sum(abs(a - b) for a, b in zip(nums, target))
# Example usage
nums = [3,5,1,2]
target = [4,6,2,4]
print(min_operations(nums, target))public class Solution {
public int minOperations(int[] nums, int[] target) {
int operations = 0;
for (int i = 0; i < nums.length; i++) {
operations += Math.abs(nums[i] - target[i]);
}
return operations;
}
public static void main(String[] args) {
int[] nums = {3, 5, 1, 2};
int[] target = {4, 6, 2, 4};
Solution sol = new Solution();
System.out.println(sol.minOperations(nums, target));
}
}#include <iostream>
#include <vector>
#include <cmath>
int min_operations(const std::vector<int>& nums, const std::vector<int>& target) {
int operations = 0;
for (size_t i = 0; i < nums.size(); ++i) {
operations += std::abs(nums[i] - target[i]);
}
return operations;
}
int main() {
std::vector<int> nums = {3, 5, 1, 2};
std::vector<int> target = {4, 6, 2, 4};
std::cout << min_operations(nums, target) << std::endl;
return 0;
}function minOperations(nums, target) {
let operations = 0;
for (let i = 0; i < nums.length; i++) {
operations += Math.abs(nums[i] - target[i]);
}
return operations;
}
// Example usage
const nums = [3, 5, 1, 2];
const target = [4, 6, 2, 4];
console.log(minOperations(nums, target));#include <stdio.h>
#include <stdlib.h>
int min_operations(int *nums, int *target, int length) {
int operations = 0;
for (int i = 0; i < length; i++) {
operations += abs(nums[i] - target[i]);
}
return operations;
}
int main() {
int nums[] = {3, 5, 1, 2};
int target[] = {4, 6, 2, 4};
int length = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", min_operations(nums, target, length));
return 0;
}using System;
public class Solution {
public int MinOperations(int[] nums, int[] target) {
int operations = 0;
for (int i = 0; i < nums.Length; i++) {
operations += Math.Abs(nums[i] - target[i]);
}
return operations;
}
public static void Main(string[] args) {
int[] nums = { 3, 5, 1, 2 };
int[] target = { 4, 6, 2, 4 };
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations(nums, target));
}
}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.
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.
def min_operations(nums, target):
operations = 0
for i in range(len(nums)):
while nums[i] != target[i]:
if nums[i] < target[i]:
nums[i] += 1
else:
nums[i] -= 1
operations += 1
return operations
# Example usage
nums = [3,5,1,2]
target = [4,6,2,4]
print(min_operations(nums, target))public class Solution {
public int minOperations(int[] nums, int[] target) {
int operations = 0;
for (int i = 0; i < nums.length; i++) {
while (nums[i] != target[i]) {
if (nums[i] < target[i])
nums[i]++;
else
nums[i]--;
operations++;
}
}
return operations;
}
public static void main(String[] args) {
int[] nums = {3, 5, 1, 2};
int[] target = {4, 6, 2, 4};
Solution sol = new Solution();
System.out.println(sol.minOperations(nums, target));
}
}#include <iostream>
#include <vector>
int min_operations(std::vector<int>& nums, const std::vector<int>& target) {
int operations = 0;
for (size_t i = 0; i < nums.size(); ++i) {
while (nums[i] != target[i]) {
if (nums[i] < target[i])
++nums[i];
else
--nums[i];
++operations;
}
}
return operations;
}
int main() {
std::vector<int> nums = {3, 5, 1, 2};
std::vector<int> target = {4, 6, 2, 4};
std::cout << min_operations(nums, target) << std::endl;
return 0;
}function minOperations(nums, target) {
let operations = 0;
for (let i = 0; i < nums.length; i++) {
while (nums[i] !== target[i]) {
if (nums[i] < target[i])
nums[i]++;
else
nums[i]--;
operations++;
}
}
return operations;
}
// Example usage
const nums = [3, 5, 1, 2];
const target = [4, 6, 2, 4];
console.log(minOperations(nums, target));#include <stdio.h>
int min_operations(int *nums, int *target, int length) {
int operations = 0;
for (int i = 0; i < length; i++) {
while (nums[i] != target[i]) {
if (nums[i] < target[i])
nums[i]++;
else
nums[i]--;
operations++;
}
}
return operations;
}
int main() {
int nums[] = {3, 5, 1, 2};
int target[] = {4, 6, 2, 4};
int length = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", min_operations(nums, target, length));
return 0;
}using System;
public class Solution {
public int MinOperations(int[] nums, int[] target) {
int operations = 0;
for (int i = 0; i < nums.Length; i++) {
while (nums[i] != target[i]) {
if (nums[i] < target[i])
nums[i]++;
else
nums[i]--;
operations++;
}
}
return operations;
}
public static void Main(string[] args) {
int[] nums = { 3, 5, 1, 2 };
int[] target = { 4, 6, 2, 4 };
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations(nums, target));
}
}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.
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:
function minimumOperations(nums: number[], target: number[]): number {
const n = nums.length;
let f = Math.abs(target[0] - nums[0]);
for (let i = 1; i < n; ++i) {
const x = target[i] - nums[i];
const y = target[i - 1] - nums[i - 1];
if (x * y > 0) {
const d = Math.abs(x) - Math.abs(y);
if (d > 0) {
f += d;
}
} else {
f += Math.abs(x);
}
}
return f;
}func minimumOperations(nums []int, target []int) int64 {
f := abs(target[0] - nums[0])
for i := 1; i < len(target); i++ {
x := target[i] - nums[i]
y := target[i-1] - nums[i-1]
if x*y > 0 {
if d := abs(x) - abs(y); d > 0 {
f += d
}
} else {
f += abs(x)
}
}
return int64(f)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}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 | – |
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. |
Frequently asked questions
Is Minimum Operations to Make Array Equal to Target easy or hard?
The problem is rated Hard because recognizing the greedy difference insight is not obvious. Once the transformation to a difference array is discovered, the implementation becomes straightforward and runs in linear time.
Minimum Operations to Make Array Equal to Target Python/Java solution
Both Python and Java implementations follow the same logic: compute the difference at each index and accumulate positive increases relative to the previous difference. This produces a concise O(n) loop without extra memory structures.
How to solve Minimum Operations to Make Array Equal to Target in O(n)?
First compute diff[i] = target[i] - nums[i]. Iterate from left to right and track the previous difference. Whenever diff[i] is greater than diff[i-1], add the increase to the operation count because new increment operations must begin. Summing these positive increases yields the minimum number of operations.
What is the best approach for Minimum Operations to Make Array Equal to Target?
The optimal approach uses a greedy difference array technique. Compute diff[i] = target[i] - nums[i] and count how much the required adjustment increases compared to the previous index. Every positive increase represents new operations that must start. This produces an O(n) time and O(1) space solution.
Is Minimum Operations to Make Array Equal to Target asked at Google/Amazon/Meta?
Problems involving difference arrays, greedy range operations, and monotonic transitions frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test whether candidates can transform range updates into prefix or difference reasoning.
What data structure is used in Minimum Operations to Make Array Equal to Target?
The solution mainly relies on arrays and a difference array transformation. Conceptually it relates to monotonic stack patterns and greedy segment processing, but the optimal implementation only needs simple variables while scanning the array.
What is the time complexity of Minimum Operations to Make Array Equal to Target?
The optimal solution runs in O(n) time because the array is processed once while comparing adjacent difference values. Only constant extra variables are used, so the space complexity is O(1).