Count Subarrays With Score Less Than K | Leetcode 2302

class Solution {
    using ll = long long;
public:
    long long countSubarrays(const vector<int>& nums, long long k) {
        ll n = nums.size();
        ll left = 0, right = 0;   // window is [left, right)
        ll sum = 0;               // sum of nums[left..right-1]
        ll count = 0;

        while (left < n) {
            // Find largest valid window
            while (right<n and (sum+nums[right])*(right-left+1) < k)
                sum += nums[right++];

            count += right - left; // All subarrays starting at `left` and ending before `right` are valid

            // Slide the window forward by removing nums[left]
            if (right == left)// If we couldn’t even include nums[left], move both pointers past it
                right++;
            else 
                sum -= nums[left];
            
            left++;
        }
        return count;
    }
};
/*
//JAVA
// Java
public class Solution {
    public long countSubarrays(int[] nums, long k) {
        int n = nums.length;
        int left = 0, right = 0;    // window is [left, right)
        long sum = 0;               // sum of nums[left..right-1]
        long count = 0;

        while (left < n) {
            // Extend right as far as valid
            while (right < n && (sum + nums[right]) * (right - left + 1) < k) {
                sum += nums[right++];
            }

            // All subarrays starting at left and ending before right are valid
            count += right - left;

            // Slide window forward
            if (right == left) {
                // Couldn't include nums[left] at all
                right++;
            } else {
                sum -= nums[left];
            }
            left++;
        }

        return count;
    }
}

#Python
# Python (LeetCode-style)
from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left = 0
        right = 0          # window is [left, right)
        curr_sum = 0       # sum of nums[left..right-1]
        count = 0

        while left < n:
            # Extend right as far as valid
            while right < n and (curr_sum + nums[right]) * (right - left + 1) < k:
                curr_sum += nums[right]
                right += 1

            # All subarrays starting at left and ending before right are valid
            count += right - left

            # Slide window forward
            if right == left:
                # Couldn't include nums[left] at all
                right += 1
            else:
                curr_sum -= nums[left]

            left += 1

        return count
*/