leetcode 1658

https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/?envType=daily-question&envId=2023-09-20
mail@pastecode.io avatar
unknown
c_cpp
7 months ago
2.0 kB
13
Indexable
Never
// AMAN JAIN MCA 2nd YEAR

// time O(N), space O(1)
// Approach: Sliding Window -> find sum of the subarray required after removing elements 
// with sum X i.e is windowSumRequired = totalSum - X, Then find the largest subarray with 
// required sum, subtract its length from total elements to get the amount of elements.
// Largest subarray because we want lease amount of elements to be removed.
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        long long windowSumRequired = -x, currentSum = nums[0], left = 0, right = 0, maxWindowLength = INT_MIN;
        for(int i = 0; i < nums.size(); ++i) {
            windowSumRequired += nums[i];
        }
        if(windowSumRequired == 0) maxWindowLength = 0;
        while(right < nums.size()) {
            if(left > right) {
                if(right + 1 < nums.size()) {
                    currentSum = currentSum + nums[++right];
                }
                else {
                    break;
                }
            }
            else {
                if(currentSum == windowSumRequired) {
                    maxWindowLength = max(maxWindowLength, right - left + 1);
                    currentSum = currentSum - nums[left++];
                    if(right + 1 < nums.size()) {
                        currentSum = currentSum + nums[++right];
                    }
                    else {
                        break;
                    }
                }
                else if(currentSum < windowSumRequired) {
                    if(right + 1 < nums.size()) {
                        currentSum = currentSum + nums[++right];
                    }
                    else {
                        break;
                    }
                }
                else {
                    currentSum = currentSum - nums[left++];
                }
            }
        }
        if(maxWindowLength == INT_MIN) return -1;
        else return nums.size() - maxWindowLength;
    }
};