Problem Statement

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.

Test Cases

Example 1:

Input: nums = [2,1,4,3,5], k = 10
Output: 6
Explanation:
The 6 subarrays having scores less than 10 are:

• [2] with score 2 * 1 = 2.
• [1] with score 1 * 1 = 1.
• [4] with score 4 * 1 = 4.
• [3] with score 3 * 1 = 3.
• [5] with score 5 * 1 = 5.
• [2,1] with score (2 + 1) * 2 = 6. Note that subarrays such as [1,4] and [4,3,5] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10. Example 2:

Input: nums = [1,1,1], k = 5
Output: 5
Explanation:
Every subarray except [1,1,1] has a score less than 5.
[1,1,1] has a score (1 + 1 + 1) * 3 = 9, which is greater than 5.
Thus, there are 5 subarrays having scores less than 5.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
1 <= k <= 10^15

Intuition

We can always compute the running sum. Once we have the sum >= k, that means, we need to reduce from the left part. Do this until we again see sum < k. The count of subarray will be right - left + 1;

Approach

• Maintain 2 pointers left, right.
• Maintain the prefix sum.
• Move the right pointer and calculate the prefix sum.
• If the prefixSum * length >= k, subtract nums[left] from the sum and move left pointer until we have a valid case again.
• Calculate the score # Complexity

• Time complexity:

  TC : O(Length of array)

• Space complexity:

  O(1) as no extra space is used.

Code

class Solution {
    public long countSubarrays(int[] nums, long k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        long prefixSum = 0;
        int left = 0;
        int right = 0;
        int length = nums.length;
        long totalCount = 0;
        while (right < length) {
            prefixSum += (long)(nums[right]);
            while (left <= right && prefixSum * (right - left + 1) >= k) {
                prefixSum -= (long)(nums[left]);
                left++;
            }
            totalCount += (right - left + 1);
            right++;
        }
        return totalCount;
    }
}