1658 LeetCode problem solution

LeetCode problem link: 1658. Minimum Operations to Reduce X to Zero


Medium level problem

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 <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

LeetCode 1658 problem: solution explanation

This problem is a classic example of the Sliding Window (Two Pointers) pattern

Instead of removing elements from the left and right, find the longest contiguous subarray to keep. If the total sum is total, the kept subarray must sum to target = total - x. The minimum number of removals is n - longestLength.

Because every nums[i] is positive, use a sliding window: expand the right boundary and shrink the left boundary while the window sum exceeds target. Whenever the window sum equals target, update the maximum window length. If target < 0 or no valid window exists, return -1. If target == 0, removing every element takes n operations.


LeetCode 1658 problem: Example

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


Step-by-step

  • total = 11 (1 + 1 + 4 + 2 + 3 = 11), so target = 11 - 5 = 6.
  • Expand the window to [1, 1, 4]: its sum is 6, so longestLength = 3 ([1, 1, 4] has 3 elements).
  • Continue scanning; no longer window sums to 6.
  • Keep [1, 1, 4] and remove 2 and 3 from the right: 5 - 3 = 2 operations.

Output: 2


LeetCode 1658 problem: complexity

  • Time complexity: O(n) - each element enters and leaves the window at most once.
  • Space complexity: O(1) - only a few variables are used.

LeetCode 1658 C++ solution

class Solution {
public:
  int minOperations(vector<int>& nums, int x) {
    int target = accumulate(nums.begin(), nums.end(), 0) - x;
    if(target < 0) return -1;

    int left = 0;
    int sum = 0; 
    int maxLength = -1;

    for(int right = 0; right < nums.size(); right++) 
    {
      sum += nums[right];

      while(sum > target) sum -= nums[left++];

      if(sum == target) maxLength = max(maxLength, right - left + 1);
    }

    return maxLength == -1 ? -1 : (int)nums.size() - maxLength;
  }
};

LeetCode 1658 Java solution

class Solution {
  public int minOperations(int[] nums, int x) {
    long total = 0;

    for(int num : nums) total += num;

    long target = total - x;

    if(target < 0) return -1;
    if(target == 0) return nums.length;

    long sum = 0;
    int left = 0, longest = -1;

    for(int right = 0; right < nums.length; right++) {
      sum += nums[right];

      while(left <= right && sum > target) {
        sum -= nums[left++];
      }

      if(sum == target) {
        longest = Math.max(longest, right - left + 1);
      }
    }

    return longest == -1 ? -1 : nums.length - longest;
  }
}

LeetCode 1658 JavaScript solution

var minOperations = function(nums, x) {
  const total = nums.reduce((sum, num) => sum + num, 0);
  const target = total - x;

  if(target < 0) return -1;
  if(target === 0) return nums.length;

  let sum = 0;
  let left = 0;
  let longest = -1;

  for(let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while(left <= right && sum > target) {
      sum -= nums[left++];
    }

    if(sum === target) {
      longest = Math.max(longest, right - left + 1);
    }
  }

  return longest === -1 ? -1 : nums.length - longest;
};

LeetCode 1658 TypeScript solution

function minOperations(nums: number[], x: number): number {
  const total = nums.reduce((sum, num) => sum + num, 0);
  const target = total - x;

  if(target < 0) return -1;
  if(target === 0) return nums.length;

  let sum = 0;
  let left = 0;
  let longest = -1;

  for(let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while (left <= right && sum > target) {
      sum -= nums[left++];
    }

    if(sum === target) {
      longest = Math.max(longest, right - left + 1);
    }
  }

  return longest === -1 ? -1 : nums.length - longest;
}

LeetCode 1658 Python solution

class Solution:
  def minOperations(self, nums: List[int], x: int) -> int:
    target = sum(nums) - x

    if target < 0:
      return -1
        
    if target == 0:
      return len(nums)

    window_sum = 0
    left = 0
    longest = -1

    for right, num in enumerate(nums):
      window_sum += num

      while left <= right and window_sum > target:
        window_sum -= nums[left]
        left += 1

      if window_sum == target:
        longest = max(longest, right - left + 1)

    return -1 if longest == -1 else len(nums) - longest