Skip to content

← leetcode

Count Subarrays With Score Less Than K

· Hard

LeetCode problem 2302

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

Simply keep track of 4 variables:

  • l, for the left index of the sliding window
  • r, for the right index of the sliding window
  • sum, for the sum of all values between l and r
  • ans, for the number of valid subarrays we have counted

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: O(n) where n is the size of nums
  • Space: O(1)

time taken

  • ７minutes and 39 seconds