1658. Minimum Operations to Reduce X to Zero

This question on LeetCode is another Slide Window problem and we can use two pointers to traverse the array to find the longest subarray whose sum equals the result of sum of elements in nums minus x. To put it simply, I drew a diagram to understand this process!

Shortest subarray (leftmost or rightmost) = nums.length - Longest subarray (SUM – X)

Question

Solution

Frist of all, we have to know how to find specific number equals the sum of the longest subarray

private static int findLongestSubIntegerArr(int[] arr, int target) {
    int i = 0, j = 0, len = arr.length;
    int currVal = 0, maxLen = 0;
    while(j < len) {
        currVal += arr[j];
        while(i <= j && currVal > target) {
            currVal -= arr[i];
            i++;
        }
        if(currVal == target) {
            maxLen = Math.max(maxLen, j - i + 1);
        }
        j++;
    }

    return (maxLen == 0) ? -1 : maxLen;
}
public static void main(String[] args) {
    int[] arr = {5, 2, 3, 1, 1};
    // expected value = 4
    System.out.println(findLongestSubIntegerArr(arr, 7));
}

Slide Window

1. Initialize and check for Edge Cases
2. Iterate through nums and every time update curSum by adding the current element nums[right]
3. If curSum exceeds target, it means that current sum is too big. So we slide the left pointer to the right by one position and minus curSum by nums[left]
4. If curSum equals target, update maxLen with the length of the current subarray, which is right - left + 1
5. After finish the loop, if maxLen is still initialized value 0, we can directly return -1. Otherwise, we return nums.length - maxLen as a result

// Time complexity is O(n)
// Space complexity is O(1)
class Solution {
    public int minOperations(int[] nums, int x) {
	// step 1.
        int target = Arrays.stream(nums).sum() - x;
        if (target == 0) {
            return nums.length;
        } else if(target < 0) {
            return -1;
        }
        
        int maxLen = 0, curSum = 0, left = 0, right = 0;
        
	// step 2.
        while(right < nums.length) {
            curSum += nums[right];
	// step 3.
            while (left <= right && curSum > target) {
                curSum -= nums[left];
                left++;
            }
	// step 4.
            if (curSum == target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
            right++;
        }
		
	// step 5.
        return maxLen == 0 ? -1:nums.length - maxLen;
    }
}