Minimum Operations To Reduce X To Zero - Leetcode Solution

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's possible, otherwise, return -1.

Solution:

We can solve the problem using a two-pointer approach. First, we calculate the sum of all elements in the array, and then we move two pointers from the beginning of the array until we find a subarray whose sum is equal to the target sum x. Then we move the left pointer to the end of the subarray and continue the search. We keep track of the minimum length of the subarray and return it as the answer.

Algorithm:

1. Calculate the sum of all elements in the array.
2. Check if the sum is less than the target x. If it is, return -1.
3. Initialize two pointers left and right at the beginning of the array.
4. Initialize a variable subarray_sum as 0.
5. Run a loop until the subarray_sum is greater than or equal to x. a. If subarray_sum is equal to x, update the answer with the length of the subarray and move left pointer to the next element. b. If subarray_sum is less than x, add the value of nums[right] to subarray_sum and move right pointer to the next element. c. If subarray_sum is greater than x, subtract the value of nums[left] from subarray_sum and move left pointer to the next element.
6. Return the minimum length of the subarray. If it is equal to nums.len() + 1, return -1.

Code:

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
        let sum = nums.iter().sum::<i32>();
        let target = sum - x;
        let mut left = 0;
        let mut subarray_sum = 0;
        let mut answer = nums.len() + 1;
        for (right, &num) in nums.iter().enumerate() {
            subarray_sum += num;
            while subarray_sum > target && left <= right {
                subarray_sum -= nums[left];
                left += 1;
            }
            if subarray_sum == target {
                answer = answer.min(nums.len() - right + left - 1);
            }
        }
        if answer > nums.len() {
            -1
        } else {
            answer as i32
        }
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

1