Minimum Operations to Reduce X to Zero

LeetCode 1776 | Difficulty: Medium

Medium

Problem Description

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 <= 10^5`

- `1 <= nums[i] <= 10^4`

- `1 <= x <= 10^9`

Topics: Array, Hash Table, Binary Search, Sliding Window, Prefix Sum

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 256 ms)

Metric	Value
Runtime	256 ms
Memory	48 MB
Date	2022-02-08

Solution

public class Solution {
    public int MinOperations(int[] nums, int x) {
        int target = nums.Sum() - x, result = Int32.MinValue, sum = 0, n = nums.Length;
    if(target== 0) return n;
    if(target == -1) return -1;
    int i = 0;
    for (int j = 0; j < n; j++)
    {
        sum += nums[j];
        while (sum >= target && i<=j)
        {
            if (sum == target)
                result = Math.Max(result, j - i + 1);
            sum -= nums[i];
            i++;
        }

    }

    return result == Int32.MinValue ? -1 : nums.Length - result;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-08) — 419 ms, 47.6 MB

public class Solution {
    public int MinOperations(int[] nums, int x) {
        int target = nums.Sum() - x, result = Int32.MinValue, sum = 0, n = nums.Length;
    if (target == 0) return n;
    if (target == -1) return -1;
    int i = 0;
    for (int j = 0; j < n; j++)
    {
        sum += nums[j];
        while (sum >= target && i <= j)
        {
            if (sum == target)
                result = Math.Max(result, j - i + 1);
            sum -= nums[i];
            i++;
        }
    }

    return result == Int32.MinValue ? -1 : nums.Length - result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray.

Hint 2: Finding the maximum subarray is standard and can be done greedily.