Count the number of contiguous subarrays whose score is less than a given threshold.
Given an integer array nums and an integer k, count how many contiguous subarrays have a score strictly less than k.
For a subarray nums[l..r], define its score as:
Return the number of subarrays whose score is less than k.
This problem is often solved by expanding a window and maintaining its running sum so you can check how many valid subarrays end at each position.
Input Format
nums: an integer arrayk: an integer threshold
You are asked to count all contiguous subarrays nums[l..r] such that sum(nums[l..r]) * (r - l + 1) < k.
Output Format
Return a single integer: the number of valid subarrays.
Constraints
1 <= nums.length <= $10^{5}$1 <= nums[i]1 <= k <= $10^{15}$
These are practice-oriented constraints consistent with the common interview formulation of the problem.
Example 1
Input
nums = [2,1,4,3,5], k = 10
Output
6
Explanation
The valid subarrays are [2], [1], [4], [3], [5], and [2,1]. Their scores are 2, 1, 4, 3, 5, and 6 respectively, all less than 10.
Example 2
Input
nums = [1,1,1], k = 5
Output
6
Explanation
All subarrays are valid because the largest score is [1,1,1] -> 3 * 3 = 9, which is not less than 5. Wait, that subarray is invalid; valid subarrays are [1], [1], [1], [1,1], [1,1]. Total = 5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.