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
.
For example:
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
:
nums[0..3]
by 1, nums = [4,6,2,3]
. The first element is incremented to 4, the second to 6, the third to 2, and the fourth to 3.nums[3..3]
by 1, nums = [4,6,2,4]
. The fourth element is incremented to 4.nums = [1,3,2], target = [2,1,4]
Output: 5
Explanation:
We will perform the following operations to make nums
equal to target
:
nums[0..0]
by 1, nums = [2,3,2]
nums[1..1]
by 1, nums = [2,2,2]
nums[1..1]
by 1, nums = [2,1,2]
nums[2..2]
by 1, nums = [2,1,3]
nums[2..2]
by 1, nums = [2,1,4]
What is the most efficient algorithm to solve this problem?
The most straightforward approach is to iterate through the arrays and, for each index, perform the necessary increment or decrement operations on subarrays starting from that index until the nums
element matches the corresponding target
element. This involves repeated subarray modifications, making it inefficient.
def min_operations_naive(nums, target):
n = len(nums)
operations = 0
for i in range(n):
diff = target[i] - nums[i]
if diff > 0:
for j in range(i, n):
nums[j] += diff
operations += diff
elif diff < 0:
for j in range(i, n):
nums[j] += diff
operations += abs(diff)
return operations
O(n^2) in the worst case, where n is the length of the arrays. This is due to the nested loops for subarray modifications.
O(1), as it modifies the input array in place.
A more efficient approach is to focus on the differences between consecutive elements. The key insight is that the number of operations needed is the sum of the absolute differences between adjacent elements in the difference array.
diff[i] = target[i] - nums[i]
.operations = abs(diff[0])
.i = 1
to n-1
and add abs(diff[i] - diff[i-1])
to operations
.operations
.def min_operations_optimal(nums, target):
n = len(nums)
operations = abs(target[0] - nums[0])
for i in range(1, n):
operations += abs(target[i] - nums[i] - (target[i-1] - nums[i-1]))
return operations
O(n), where n is the length of the arrays. We iterate through the arrays once.
O(1), as it only uses a constant amount of extra space.
nums
and target
.long
in Java/C++ or handle it via modulo if the constraints allow).The optimal solution provides a significant improvement in time complexity compared to the naive approach. By focusing on the differences between consecutive elements, it avoids the need for repeated subarray modifications.