2302. Count Subarrays With Score Less Than K

The score of an array is defined as the product of its sum and its length.

• For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

• two pointer solution
• Time : O(n)
• Space : O(n)

class Solution {
public:
    long long countSubarrays(vector<int>& A, long long k) {
        vector<long long> psum{0};
        long long res = 0, l = 0, n = A.size();
        for(int i = 0; i < n; i++) {
            psum.push_back(psum.back() + A[i]);
            while((psum.back() - psum[l]) * (i - l + 1) >= k) l++;
            res += (i - l + 1);
        }
        return res;
    }
};

• binary search solution
• Time : O(nlogn)
• Space : O(n)

class Solution {
    long long query(vector<long long>& A, long long k) {
        long long l = 0, r = A.size() - 1, res = 0;
        while(l <= r) {
            int m = l + (r - l) / 2;
            long long mul = (A.back() - A[m]) * (A.size() - m - 1);
            if(mul < k) {
                res = max(res, (long long)(A.size() - m - 1));
                r = m - 1;
            } else l = m + 1;
        }
        return res;
    }
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        vector<long long> psum{0};
        long long res = 0;
        for(auto & n : nums) {
            psum.push_back(psum.back() + n);
            res += query(psum, k);
        }
        return res;
    }
};