Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

All values are positive, so shrinking a window decreases both its sum and length, and therefore its score. Once a window ending at right has score below k, every suffix ending there is valid too.

Approach

Maintain a window sum and left boundary. Add each new rightmost value, then remove leftmost values while sum * length >= k. After restoring the strict condition, add the window length to the answer, counting every valid starting position for this right endpoint. A window may become empty when even its final singleton is too large. Return the total; each subarray is counted at its own right endpoint.

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        acc = 0
        res = 0
        l = 0

        for r in range(n):
            #1. add to acc
            acc += nums[r]
            while acc * (r - l + 1) >= k:
                acc -= nums[l]
                l += 1
            #2. add subarrays
            res += r - l + 1

        return res

Complexity analysis

Let n = nums.length. Time: O(n), because both window pointers advance at most n times. Auxiliary space: O(1).