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 <= 109Problem Overview: You are given an array nums and an integer x. In one operation you remove the leftmost or rightmost element from the array and subtract its value from x. The goal is to reduce x to exactly zero using the minimum number of operations.
The key observation: removing elements from both ends is equivalent to keeping a contiguous middle subarray. If the total sum of the array is total, the removed elements must sum to x, meaning the remaining subarray must sum to total - x. The task becomes finding the longest subarray with that sum.
Approach 1: Sliding Window for the Complement (O(n) time, O(1) space)
This is the optimal approach and the one most interviewers expect. First compute target = totalSum - x. Instead of thinking about removing elements, search for the longest subarray whose sum equals target. Use a classic sliding window with two pointers. Expand the right pointer while accumulating the window sum, and shrink the left pointer whenever the sum exceeds the target. When the window sum equals the target, record the maximum length. If the longest valid subarray length is L, the minimum operations equals n - L. This works because all values are positive, allowing the window to move monotonically.
Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)
Another way to find the longest subarray with sum target uses prefix sums and a hash table. Maintain a running prefix sum while iterating through the array. Store the earliest index where each prefix sum appears. If the current prefix sum is curr, check whether curr - target exists in the map. If it does, the elements between those indices form a valid subarray with the desired sum. Track the maximum length seen. This approach works for more general arrays but uses extra memory for the hash map.
Approach 3: Dynamic Programming (O(n * x) time, O(x) space)
A dynamic programming formulation treats the problem as choosing elements from the left or right to reach sum x. Define dp[s] as the minimum operations needed to reach sum s. Iteratively update states as you consider elements from both ends. While this approach demonstrates the problem’s combinational nature, it becomes inefficient when x is large. For typical constraints, the sliding window strategy is significantly faster and simpler.
Recommended for interviews: The sliding window complement trick is the expected solution. It reduces the original problem to a longest subarray search in O(n) time and constant space. Mentioning the prefix-sum alternative shows broader understanding, while the sliding window demonstrates strong problem transformation skills.
To 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.
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.
Python
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.
According to the problem description, we need to remove elements from both ends of the array nums so that the sum of the removed elements equals x, and the number of removed elements is minimized. We can transform the problem into: find the longest consecutive subarray in the array nums such that the sum of the subarray s = sum_{i=0}^{n} nums[i] - x. In this way, we can transform the problem into finding the length mx of the longest consecutive subarray in the array nums with a sum of s, and the answer is n - mx.
We initialize mx = -1, and then use a hash table vis to store the prefix sum, where the key is the prefix sum and the value is the index corresponding to the prefix sum.
Traverse the array nums, for the current element nums[i], calculate the prefix sum t, if t is not in the hash table, add t to the hash table; if t - s is in the hash table, update mx = max(mx, i - vis[t - s]).
Finally, if mx = -1, return -1, otherwise return n - mx.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Based on the analysis of Solution 1, we need to find the length mx of the longest consecutive subarray in the array nums with a sum of s. Since all elements in the array nums are positive integers, the prefix sum of the array will only increase monotonically, so we can use two pointers to solve this problem.
We initialize pointer j = 0, prefix sum t = 0, and the length of the longest consecutive subarray mx = -1.
Traverse the array nums, for the current element nums[i], calculate the prefix sum t += nums[i]. If t > s, then move the pointer j until t leq s. If t = s, then update mx = max(mx, i - j + 1).
Finally, if mx = -1, return -1, otherwise return n - mx.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| 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. |
| Hash Table + Prefix Sum | — |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window (Complement Subarray) | O(n) | O(1) | Best choice when array values are positive and you need the optimal interview solution |
| Prefix Sum + Hash Map | O(n) | O(n) | General technique for longest subarray with given sum |
| Dynamic Programming | O(n * x) | O(x) | Useful for conceptual understanding when modeling choices from both ends |
Minimum Operations to Reduce X to Zero - Leetcode 1658 - Python • NeetCodeIO • 20,743 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