Count Subarrays with Score Below K
Given an array nums of positive integers and an integer k, the score of a subarray is (sum of its elements) × (its length). Count the non-empty contiguous subarrays whose score is strictly less than k.
nums = [2, 1, 4, 3, 5], k = 10 => 6
[2]=2, [1]=1, [4]=4, [3]=3, [5]=5, [2,1] = 3×2 = 6
([1,4] = 5×2 = 10 is not < 10)
nums = [1, 1, 1], k = 5 => 5
[1], [1], [1], [1,1], [1,1] ([1,1,1] = 3×3 = 9)n up to 10^5, values up to 10^5, k up to 10^15 — target O(n).
Hints
Hint 1
With positive values, fixing the right end and moving the left end rightward strictly shrinks both the sum and the length — so the score is monotone and valid left ends form a suffix.
Hint 2
Keep a window [left, right] with score < k: for each right, shrink from the left while sum × length >= k, then every start in [left, right] works — add right − left + 1.