Minimum Operations to Make Array Equal to Target - Solution & Explanation

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.