LeetCode 3229 - Minimum Operations to Make Array Equal to Target

LeetCode Problem 3229

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Stack, Greedy, Monotonic Stack

Solution

Problem Understanding

The problem gives us two arrays, nums and target, both of the same length. We are allowed to perform operations on nums until it becomes exactly equal to target.

In one operation, we choose any contiguous subarray and either:

• Increment every element in that subarray by 1
• Decrement every element in that subarray by 1

The goal is to compute the minimum number of such operations needed.

A useful way to think about the problem is to focus on the difference between the two arrays. For every index i, define:

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

If diff[i] > 0, that position needs increments.

If diff[i] < 0, that position needs decrements.

If diff[i] == 0, that position already matches.

The important observation is that one operation affects an entire contiguous segment uniformly. This means operations can be shared across neighboring positions when they require changes in the same direction.

For example:

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

diff   = [1,1,1,2]

The first three positions all need one increment, so a single operation can cover them together. The last position needs one extra increment beyond that, so it requires another operation.

The constraints are large:

• n can be up to 10^5
• values can be up to 10^8

This immediately tells us that any quadratic solution is too slow. We need an algorithm close to linear time.

Several edge cases are important:

• Arrays that are already equal
• Alternating positive and negative differences
• Large continuous segments requiring the same direction
• Single-element arrays
• Sudden jumps in required adjustment amounts

The problem guarantees:

• Both arrays have equal length
• All values are positive integers
• Length is at least 1

This removes concerns about invalid input or mismatched array sizes.

Approaches

Brute Force Approach

A brute force strategy would try to simulate operations directly.

We could repeatedly locate segments that still need increments or decrements, apply an operation to some chosen subarray, and continue until all differences become zero.

For example, if:

diff = [1,1,1,2]

we might increment the entire prefix, then increment the final element.

While this eventually works, the challenge is choosing the optimal segments. A naive implementation might repeatedly scan the array, modify ranges, and update values one step at a time.

In the worst case, values can differ by as much as 10^8, so explicit simulation becomes infeasible.

Even if we optimize segment selection, repeated updates over large ranges lead to quadratic behavior.

Key Insight

The crucial observation is that operations only matter when the required adjustment increases.

Suppose we look at the positive differences only:

diff = [1,1,3,2]

Interpretation:

• Position 0 starts needing 1 increment operation
• Position 1 still needs only 1, so no new operation is required
• Position 2 now needs 3, meaning we must start 2 additional operations here
• Position 3 drops to 2, so no extra operation is needed

The same logic applies independently for negative values.

This transforms the problem into counting how many new operations must begin as we scan left to right.

More formally:

• If current and previous differences have opposite signs, sharing is impossible
• If they have the same sign, only the increase beyond the previous magnitude requires new operations

This leads to a greedy linear solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × maxDiff) or worse	O(n)	Explicitly simulates operations
Optimal	O(n)	O(1)	Counts only newly required operations

Algorithm Walkthrough

Step 1: Build the Difference Array Conceptually

For every index:

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

Positive values mean increments are needed.

Negative values mean decrements are needed.

Zero means no work is needed.

We do not actually need to store the full array, we can compute values on the fly.

Step 2: Initialize the Answer

The first position determines the initial number of operations needed.

If:

diff[0] = 5

then we need 5 increment operations starting at index 0.

If:

diff[0] = -4

then we need 4 decrement operations starting at index 0.

So:

answer = abs(diff[0])

Step 3: Scan Left to Right

For every new position, compare the current difference with the previous one.

There are two major cases.

Case A: Different Signs

Example:

prev = 3
curr = -2

Increment operations cannot help decrement operations.

All previous operations stop contributing.

We must start 2 completely new decrement operations.

So we add:

abs(curr)

Case B: Same Sign

Example:

prev = 2
curr = 5

The previous 2 operations can continue into this index.

But we still need 3 more operations.

So we add:

curr - prev

only if this value is positive.

Similarly:

prev = -2
curr = -5

requires 3 extra decrement operations.

Step 4: Accumulate the Total

At each step:

• Add only newly required operations
• Reuse existing operations whenever possible

The accumulated total becomes the minimum answer.

Why it works

The algorithm works because operations can extend across adjacent positions only when those positions require adjustments in the same direction.

When the required magnitude increases, new operations must begin.

When the magnitude decreases, existing operations can simply stop earlier.

Therefore, the minimum number of operations equals the total number of times additional operations must start while scanning left to right.

This greedy strategy is optimal because extending an existing operation is always better than starting a new one.

Python Solution

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        previous = target[0] - nums[0]
        operations = abs(previous)

        for i in range(1, len(nums)):
            current = target[i] - nums[i]

            # Different signs, cannot share operations
            if (current > 0 and previous < 0) or (current < 0 and previous > 0):
                operations += abs(current)

            # Same positive direction
            elif current > 0 and previous > 0:
                operations += max(0, current - previous)

            # Same negative direction
            elif current < 0 and previous < 0:
                operations += max(0, abs(current) - abs(previous))

            previous = current

        return operations

The implementation follows the greedy observation directly.

We first compute the difference at index 0. Its absolute value represents how many operations must start initially.

Then we iterate through the remaining indices.

At each position, we compare the current difference with the previous difference.

If the signs differ, operations cannot continue across the boundary, so the current magnitude must start entirely new operations.

If the signs are the same, we only add the increase in required magnitude because existing operations can continue.

The algorithm never simulates actual range operations. Instead, it counts how many operations must begin, which is exactly the minimal answer.

Go Solution

func minimumOperations(nums []int, target []int) int64 {
    previous := target[0] - nums[0]
    operations := int64(abs(previous))

    for i := 1; i < len(nums); i++ {
        current := target[i] - nums[i]

        // Different signs
        if (current > 0 && previous < 0) || (current < 0 && previous > 0) {
            operations += int64(abs(current))

        // Same positive direction
        } else if current > 0 && previous > 0 {
            if current > previous {
                operations += int64(current - previous)
            }

        // Same negative direction
        } else if current < 0 && previous < 0 {
            if abs(current) > abs(previous) {
                operations += int64(abs(current) - abs(previous))
            }
        }

        previous = current
    }

    return operations
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go implementation mirrors the Python logic closely.

One important difference is the use of int64 for the answer. Since the total number of operations can exceed the range of a 32-bit integer, using int64 prevents overflow.

Go slices naturally handle dynamic array access, so no special handling is needed for empty arrays because the constraints guarantee at least one element.

Worked Examples

Example 1

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

Difference array:

diff = [1,1,1,2]

Index	Current Diff	Previous Diff	Additional Operations	Total
0	1	N/A	1	1
1	1	1	0	1
2	1	1	0	1
3	2	1	1	2

Final answer:

2

Example 2

nums   = [1,3,2]
target = [2,1,4]

Difference array:

diff = [1,-2,2]

Index	Current Diff	Previous Diff	Additional Operations	Total
0	1	N/A	1	1
1	-2	1	2	3
2	2	-2	2	5

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the arrays
Space	O(1)	Only a few variables are used

The algorithm processes each index exactly once and performs only constant-time work per iteration.

No auxiliary arrays, stacks, or dynamic programming tables are required, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        previous = target[0] - nums[0]
        operations = abs(previous)

        for i in range(1, len(nums)):
            current = target[i] - nums[i]

            if (current > 0 and previous < 0) or (current < 0 and previous > 0):
                operations += abs(current)

            elif current > 0 and previous > 0:
                operations += max(0, current - previous)

            elif current < 0 and previous < 0:
                operations += max(0, abs(current) - abs(previous))

            previous = current

        return operations

s = Solution()

assert s.minimumOperations([3,5,1,2], [4,6,2,4]) == 2
# Basic increasing segment sharing

assert s.minimumOperations([1,3,2], [2,1,4]) == 5
# Alternating signs

assert s.minimumOperations([1], [1]) == 0
# Single element already equal

assert s.minimumOperations([1], [5]) == 4
# Single element increment

assert s.minimumOperations([5], [1]) == 4
# Single element decrement

assert s.minimumOperations([1,1,1], [2,2,2]) == 1
# Entire array can be updated together

assert s.minimumOperations([1,1,1], [2,3,4]) == 4
# Increasing positive requirements

assert s.minimumOperations([5,5,5], [4,3,2]) == 3
# Increasing negative requirements

assert s.minimumOperations([1,2,3], [1,2,3]) == 0
# Arrays already equal

assert s.minimumOperations([1,2,3], [3,2,1]) == 4
# Mixed directions

assert s.minimumOperations([10,10,10], [1,1,1]) == 9
# Large uniform decrement

assert s.minimumOperations([1,1,1,1], [2,1,2,1]) == 2
# Separate increment regions

Test Summary

Test	Why
[3,5,1,2] -> [4,6,2,4]	Basic shared increment operations
[1,3,2] -> [2,1,4]	Alternating positive and negative differences
Single equal element	Minimum boundary case
Single increment element	Single-position increase
Single decrement element	Single-position decrease
Uniform increment array	Entire range handled together
Increasing positive needs	Tests incremental operation growth
Increasing negative needs	Tests decrement growth
Already equal arrays	Verifies zero operations
Mixed directions	Ensures sign changes handled correctly
Large uniform decrement	Large magnitude operations
Multiple separated regions	Verifies independent segments

Edge Cases

Arrays Already Equal

If every element already matches:

nums = [1,2,3]
target = [1,2,3]

then every difference is zero.

A buggy implementation might accidentally count