leetcode – 2302. Count Subarrays With Score Less Than K

Descript ion

The score of an arr ay is define d as the pro duct of its sum and its length.

For exa mple, 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 seq uence of elements within an array.

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.

Con straints:

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

Solution

Solved after help.

Slid in g window, when the sco re of the subarray is not less than k, shrink the window. Since we need to calculate the number of the subarray, every time we expand the window, calculate the number of subarray with nums[j] as the end ing element.

Time complexity:

(

)

o(n)

$o (n)$
Space complexity:

(

)

o(1)

$o (1)$

Code

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        cur_sum, res = 0, 0
        i = 0
        for j in range(len(nums)):
            cur_sum += nums[j]
            while cur_sum * (j - i + 1) >= k:
                cur_sum -= nums[i]
                i += 1
            # j - i + 1 is the number of subarray with nums[j] as the ending element
            res += j - i + 1
        return res