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 <= 1051 <= nums[i] <= 1041 <= x <= 109To make the problem simpler, we first calculate the total sum of the array, and then look for the longest subarray whose sum is equal to totalSum - x. This is because removing elements to get a sum of x is equivalent to finding a subarray with this complementary sum.
If we find this subarray, the number of operations is the total length of the array minus the length of this subarray. We use a sliding window to find the longest subarray with the target sum.
The given C code uses a sliding window technique. We maintain a window `[left, right)` where we continually add nums[right] to the current sum. If it exceeds our target, we shrink the window from the left until it is valid. We update our maximum length if the sum matches the target. Finally, we return the number of operations, which is the size of the array minus the longest subarray length found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array. This is because each element is processed at most twice (once added and once removed).
Space Complexity: O(1), as we only use a few extra variables.
This alternative method uses dynamic programming to explore all possible choices at any instance, storing results for optimal decisions. We define a DP array dp[i] that represents the minimum operations needed to reduce x using the first i elements from either side. We initialize by removing elements and updating DP states iteratively.
We optimize storage by using only needed previous state references, ensuring computations are rapid and effective. This dynamic programming approach is relatively complex due to combination subproblems hence less preferable but a dividing strategy worth studying.
The Python solution leverages dynamic programming using a 1D array. As we iterate through nums, each element influences potential sums achievable by contributing to subsets, thus establishing a table of values dp representing the maximum number achieved at every potential sum. The solution emerges when final target accessibility is evaluated post iterations.
Time Complexity: O(n*m), where n is the total number and m denotes max target value.
Space Complexity: O(m) in size for storage structures.
| Approach | Complexity |
|---|---|
| Sliding Window for the Complement | Time Complexity: O(n), where n is the length of the array. This is because each element is processed at most twice (once added and once removed). Space Complexity: O(1), as we only use a few extra variables. |
| Dynamic Programming | Time Complexity: O(n*m), where n is the total number and m denotes max target value. Space Complexity: O(m) in size for storage structures. |
Minimum Operations to Reduce X to Zero | O(N) Optimal | Leetcode #1658 • Techdose • 19,691 views views
Watch 9 more video solutions →Practice Minimum Operations to Reduce X to Zero with our built-in code editor and test cases.
Practice on FleetCode