DDSA Solutions

1658. Minimum Operations to Reduce X to Zero

MediumView on LeetCode
ArrayHash TableSliding WindowPrefix Sum

Problem Overview

Each operation removes one value from the left end or the right end, and the removed values must sum to x.

Intuition

Each operation removes one value from the left end or the right end, and the removed values must sum to x. What stays is one contiguous middle. Because every value is positive, the longest middle that sums to total minus x is exactly the piece you should keep, and the number of operations is the length you throw away.

Algorithm

  1. 1Add every nums[i] to get total.
  2. 2Let target = total - x. If target is negative, return -1. If it is zero, return n.
  3. 3Slide a window [l, r]: add nums[r], and while the window sum exceeds target, subtract nums[l] and advance l.
  4. 4Whenever the window sum equals target, record the maximum window length.
  5. 5Return n minus that length, or -1 when no window hit the target.

Example Walkthrough

Input: nums = [1,1,4,2,3], x = 5

  1. 1.The array sums to 11, so the middle must sum to 6.
  2. 2.The window [1,1,4] has length 3 and sum 6.
  3. 3.Two end values, 2 and 3, are removed.

Output: 2

Common Pitfalls

  • •Operations only take from the two ends, so the kept part must be one subarray.
  • •Positive values make the sliding window valid; a prefix map is unnecessary.
  • •target 0 means the whole array is removed, so the answer is n.
  • •If x is larger than the array sum, return -1.
1658.cs
C#
// Approach: Removing a prefix and a suffix that sum to x is the same as
// keeping a middle subarray that sums to total - x. Because every nums[i]
// is positive, a sliding window finds the longest such middle. The answer
// is n minus that length, or -1 when no window hits the target.
// Complexity: O(n) time, O(1) extra space.
public class Solution
{
    public int MinOperations(int[] nums, int x)
    {
        int n = nums.Length;
        int total = 0;
        for (int i = 0; i < n; i++)
            total += nums[i];

        int target = total - x;
        if (target < 0)
            return -1;
        if (target == 0)
            return n;

        int maxLen = -1;
        int sum = 0;
        for (int l = 0, r = 0; r < n; r++)
        {
            sum += nums[r];
            while (sum > target)
                sum -= nums[l++];
            if (sum == target)
                maxLen = Math.Max(maxLen, r - l + 1);
        }

        return maxLen == -1 ? -1 : n - maxLen;
    }
}
Was this solution helpful?

Related Problems