1658. Minimum Operations to Reduce X to Zero

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: str1 = "nums = [1,1,4,2,3], x = 5", str2 = "2" Output: 2

Input: nums = [5,6,7,8,9], x = 4 Output: -1

Input: nums = [3,2,20,1,1,3], x = 10 Output: 5

Solution Approach

The algorithm utilizes a sliding window technique to find the minimum number of operations to reduce ‘x’ to zero by considering all possible contiguous subarrays.

Algorithm

1. Initialization and Validation: Initialize variables and check if it’s possible to achieve ‘x’ from the total sum of the array.
2. Sliding Window Approach: Utilize a sliding window technique to find contiguous subarrays with a sum equal to ‘x’.
3. Return Minimum Operations: Return the minimum number of operations if a valid subarray is found; otherwise, return -1.

Implement

    class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
      n = len(nums)
      total = sum(nums)
      if total < x:
          return -1
      r = 0
      min_n = n + 1
      lsum = 0
      rsum = total
      for l in range(-1, n - 1):
          if l != -1:
              lsum += nums[l]
          while r < n and lsum + rsum > x:
              rsum -= nums[r]
              r += 1
          if lsum + rsum == x:
              min_n = min(min_n, l + 1 + n - r)
      return -1 if min_n > n else min_n
     

    
    

Twitter  facebook  Email