Minimum Operations to Reduce X to Zero — Problem & Solution
Minimum Operations to Reduce X to Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Operations to Reduce X to Zero is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Binary Search, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and an integer x. In one operation you remove either the leftmost or the rightmost element of nums and subtract its value from x.
Return the minimum number of operations that reduces x to exactly 0, or -1 if that is impossible.
Example 1
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: Remove the last two elements: 3 + 2 = 5.
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: Remove 3, 2 from the front and 3, 1, 1 from the back.
Constraints
1 <= nums.length <= 401 <= nums[i] <= 1001 <= x <= 1000000
Hints for Minimum Operations to Reduce X to Zero
Hint 1
Removing from both ends leaves a contiguous middle. Flip the problem around and look at what stays.
Hint 2
The kept middle must sum to
total - x; minimising removals means maximising that middle's length.Hint 3
All values are positive, so a sliding window finds the longest subarray with a given sum in one pass.
How to solve Minimum Operations to Reduce X to Zero
Removing from both ends leaves a contiguous middle, so find the longest subarray summing to total - x; the operations are everything outside it.
Approach
- Compute
target = total - x; return-1if negative,nif zero. - Slide a window: extend
right, then shrink from the left while the sum exceedstarget. - Whenever the sum equals
target, record the window length. - Return
n - bestLength, or-1if no window matched.
Why it works
Values are positive, so window sums are monotone in both endpoints and the two-pointer sweep finds every subarray with the exact sum. Minimising removals is the same as maximising what is kept.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
target == 0means everything must be removed — answern, not0.- A hash map of prefix sums handles the same search when negatives are allowed.
Reference solution
Python
def minOperations(nums, x: int) -> int:
target = sum(nums) - x
if target < 0:
return -1
if target == 0:
return len(nums)
left = total = 0
best = -1
for right, value in enumerate(nums):
total += value
while total > target and left <= right:
total -= nums[left]
left += 1
if total == target:
best = max(best, right - left + 1)
return -1 if best == -1 else len(nums) - bestJava
public static int minOperations(int[] nums, int x) {
int total = 0;
for (int v : nums) total += v;
int target = total - x;
if (target < 0) return -1;
if (target == 0) return nums.length;
int left = 0, sum = 0, best = -1;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left];
left++;
}
if (sum == target) best = Math.max(best, right - left + 1);
}
return best == -1 ? -1 : nums.length - best;
}C++
int minOperations(vector<int>& nums, int x) {
int total = 0;
for (int v : nums) total += v;
int target = total - x;
if (target < 0) return -1;
if (target == 0) return (int) nums.size();
int left = 0, sum = 0, best = -1;
for (int right = 0; right < (int) nums.size(); right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left];
left++;
}
if (sum == target) best = max(best, right - left + 1);
}
return best == -1 ? -1 : (int) nums.size() - best;
}JavaScript
var minOperations = function(nums, x) {
let total = 0;
for (let i = 0; i < nums.length; i++) total += nums[i];
const target = total - x;
if (target < 0) return -1;
if (target === 0) return nums.length;
let left = 0, sum = 0, best = -1;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left];
left++;
}
if (sum === target) {
const len = right - left + 1;
if (len > best) best = len;
}
}
return best === -1 ? -1 : nums.length - best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets