Minimum Operations to Reduce X to Zero

Medium
248.

Minimum Operations to Reduce X to Zero

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.

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 <= 40
  • 1 <= nums[i] <= 100
  • 1 <= x <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function(nums, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 1 <= nums[i] <= 100
  • 1 <= x <= 1000000

Hints for Minimum Operations to Reduce X to Zero

  1. Hint 1

    Removing from both ends leaves a contiguous middle. Flip the problem around and look at what stays.

  2. Hint 2

    The kept middle must sum to total - x; minimising removals means maximising that middle's length.

  3. 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

  1. Compute target = total - x; return -1 if negative, n if zero.
  2. Slide a window: extend right, then shrink from the left while the sum exceeds target.
  3. Whenever the sum equals target, record the window length.
  4. Return n - bestLength, or -1 if 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 == 0 means everything must be removed — answer n, not 0.
  • 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) - best

Java

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