Minimum Operations to Make Array Equal to Target

Minimum Operations to Make Array Equal to Target - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,5,1,2], target = [4,6,2,4]

› Output: 7

💡 Note: We need to transform [3,5,1,2] to [4,6,2,4]. Optimal operations: increment subarray [0,1] by 1, increment subarray [2,3] by 1, then increment subarray [3,3] by 2. Total: 2 + 2 + 2 + 1 = 7 operations.

Example 2 — All Same Target

$ Input: nums = [1,3,2], target = [2,1,4]

› Output: 5

💡 Note: Transform [1,3,2] to [2,1,4]: increment nums[0] by 1, decrement nums[1] by 2, increment nums[2] by 2. Operations: 1 + 2 + 2 = 5.

Example 3 — Already Equal

$ Input: nums = [1,2,3], target = [1,2,3]

› Output: 0

💡 Note: Arrays are already equal, no operations needed.

Constraints

1 ≤ nums.length == target.length ≤ 10⁵
1 ≤ nums[i], target[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums = [3,5,1,2] and target = [4,6,2,4]

Calculate Differences

Find diff[i] = target[i] - nums[i] for each position

Optimal Operations

Use subarray operations to minimize total operations

Key Takeaway

🎯 Key Insight: Separate positive and negative differences to optimize subarray operations

Asked in

G Google 45 f Meta 38 a Amazon 32 m Microsoft 28

The key insight is to process positive and negative differences separately using two passes. The optimal approach handles increments and decrements independently to minimize total operations. Best approach uses two-pass greedy algorithm. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Difference Array	O(n)	O(n)	Calculate difference array and process operations greedily from left to right
Brute Force	O(n)	O(1)	Process each position individually by calculating required operations
Monotonic Stack (Optimal)	O(n)	O(n)	Use monotonic stack to efficiently handle positive and negative differences separately

Greedy with Difference Array — Algorithm Steps

Create difference array diff[i] = target[i] - nums[i]
Process left to right, tracking cumulative sum
Add operations when difference increases

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Differences

Calculate diff[i] = target[i] - nums[i]

Track Cumulative

Process left to right, track current level

Add Operations

Add operations when level increases

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int numsSize, int* target, int targetSize) {
    int* diff = malloc(numsSize * sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        diff[i] = target[i] - nums[i];
    }
    
    long long operations = 0;
    int current = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (diff[i] > current) {
            operations += diff[i] - current;
        }
        current = diff[i];
    }
    
    free(diff);
    return operations;
}

int* parseArray(char* s, int* size) {
    int* arr = malloc(1000 * sizeof(int));
    *size = 0;
    char* token = strtok(s + 1, ",]");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    return arr;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    
    int numsSize, targetSize;
    int* nums = parseArray(line1, &numsSize);
    int* target = parseArray(line2, &targetSize);
    
    printf("%lld\n", solution(nums, numsSize, target, targetSize));
    
    free(nums);
    free(target);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to calculate differences and cumulative operations

✓ Linear Growth

Space Complexity

O(n)

Extra array to store differences

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Difference Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler