Minimum Operations to Reduce X to Zero
Medium · Arrays & Hashing · Array · Hash Table · Binary Search · Sliding Window · Prefix Sum
Problem
You are given an array of positive integers nums and an integer x. One operation removes either the leftmost or the rightmost element of nums and subtracts its value from x. The array shrinks with each operation.
Return the minimum number of operations that bring x to exactly 0, or -1 if it cannot be done.
Examples
Input: nums = [2,4,1,1,3], x = 5 Output: 2
Remove 2 from the left and 3 from the right.
Input: nums = [6,7,8], x = 4 Output: -1
Every element is larger than 4, so no removal works.
Input: nums = [1,2,3], x = 6 Output: 3
All three elements must be removed.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^4
- 1 <= x <= 10^9
Approaches
- Try every number of left removals — time O(n^2), space O(1)
Follow-up
With negative numbers the sliding window breaks (shrinking can raise the sum); use prefix sums and a hash map of the first index for each prefix sum instead, still O(n). The first use case does exactly that; the second relaxes "exactly x" to "at least x".
Related problems
Start free on Cariara · Coding problems · System design studio
