1658. Minimum Operations to Reduce X to Zero LeetCode Solution
In this guide, you will get 1658. Minimum Operations to Reduce X to Zero LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Reduce X to Zero problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Operations to Reduce X to Zero
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.
1658. Minimum Operations to Reduce X to Zero LeetCode Solution in C++
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
const int targetSum = accumulate(nums.begin(), nums.end(), 0) - x;
if (targetSum == 0)
return nums.size();
const int maxLen = maxSubArrayLen(nums, targetSum);
return maxLen == -1 ? -1 : nums.size() - maxLen;
}
private:
// Same as 325. Maximum Size Subarray Sum Equals k
int maxSubArrayLen(vector<int>& nums, int k) {
int res = -1;
int prefix = 0;
unordered_map<int, int> prefixToIndex{{0, -1}};
for (int i = 0; i < nums.size(); ++i) {
prefix += nums[i];
const int target = prefix - k;
if (const auto it = prefixToIndex.find(target);
it != prefixToIndex.cend())
res = max(res, i - it->second);
// No need to check the existence of the prefix since it's unique.
prefixToIndex[prefix] = i;
}
return res;
}
}; /* code provided by PROGIEZ */
1658. Minimum Operations to Reduce X to Zero LeetCode Solution in Java
class Solution {
public int minOperations(int[] nums, int x) {
final int targetSum = Arrays.stream(nums).sum() - x;
if (targetSum == 0)
return nums.length;
final int maxLen = maxSubArrayLen(nums, targetSum);
return maxLen == -1 ? -1 : nums.length - maxLen;
}
// Same as 325. Maximum Size Subarray Sum Equals k
private int maxSubArrayLen(int[] nums, int k) {
int res = -1;
int prefix = 0;
Map<Integer, Integer> prefixToIndex = new HashMap<>();
prefixToIndex.put(0, -1);
for (int i = 0; i < nums.length; ++i) {
prefix += nums[i];
final int target = prefix - k;
if (prefixToIndex.containsKey(target))
res = Math.max(res, i - prefixToIndex.get(target));
// No need to check the existence of the prefix since it's unique.
prefixToIndex.put(prefix, i);
}
return res;
}
} // code provided by PROGIEZ
1658. Minimum Operations to Reduce X to Zero LeetCode Solution in Python
class Solution:
def minOperations(self, nums: list[int], x: int) -> int:
targetSum = sum(nums) - x
if targetSum == 0:
return len(nums)
maxLen = self._maxSubArrayLen(nums, targetSum)
return -1 if maxLen == -1 else len(nums) - maxLen
# Same as 325. Maximum Size Subarray Sum Equals k
def _maxSubArrayLen(self, nums: list[int], k: int) -> int:
res = -1
prefix = 0
prefixToIndex = {0: -1}
for i, num in enumerate(nums):
prefix += num
target = prefix - k
if target in prefixToIndex:
res = max(res, i - prefixToIndex[target])
# No need to check the existence of the prefix since it's unique.
prefixToIndex[prefix] = i
return res # code by PROGIEZ
