Minimum Operations to Reduce X to Zero — LeetCode
2 min readJun 11, 2022
Description
You are given an integer array nums
and an integer x
. In one operation, you can either remove the leftmost or the rightmost element from the array nums
and subtract its value from x
. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x
to exactly 0
if it is possible, otherwise, return -1
.
Example 1:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
Example 2:
Input: nums = [5,6,7,8,9], x = 4
Output: -1
Example 3:
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109
Solution
Use a sliding window approach to find the maximum length subarray having the sum = arraySum — target
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int target = accumulate(nums.begin(), nums.end(), -x);
int mx = 0, n = nums.size(), l = 0, sum = 0;
if (target < 0)
return -1;
if (target == 0)
return n;
for (int r = 0; r < n; r++) {
sum += nums[r];
while (sum > target && l < r)
sum -= nums[l++];
if (sum == target)
mx = max(mx, r - l + 1);
}
return mx ? n - mx : -1;
}
};
- Time Complexity: O(n)
- Space Complexity: O(1)