2302: Count-Subarrays-With-Score-Less-Than-K
Hard

table of contents

This question is a classic two pointers / sliding window problem.

Simply keep track of 4 variables:

Now, note that, for any l, if we find the maximum valid array beginning on index l, then it implies that all subarrays are also valid. Unfortunately, however, if we count all the valid subarrays every time we increment l, we will start counting duplicate subarrays. Therefore, the algorithm just counts all the valid subarrays containing the index we want to remove from the sliding window (which in our case is always l).

code

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long l = 0, r = 0, sum = 0, ans = 0;
        for (; l < nums.size();) {
            // keep incrementing `r` if the sliding window is still valid
            for (; r < nums.size() && (sum+nums[r]) * (r-l+1) < k; ++r) {
                sum += nums[r];
            }
            // add the number of subarrays containing `nums[l]`
            ans += r-l;
            if (l == r) {
                //implies that we have not added `nums[r]` to `sum`
                ++r;
            } else {
                //implies that we have added `nums[r]` to `sum`
                sum -= nums[l];
            }
            ++l;
        }
        return ans;
    }
};

complexity

time taken