Count Subarrays With Score Less Than K
Count subarrays where (sum × length) < k, using a sliding window over positive integers.
3 min read
sliding-window array
Problem#
For nums of positive integers, the score of a subarray is its sum multiplied by its length. Count subarrays whose score is strictly less than k.
Examples#
nums = [2,1,4,3,5], k = 10→6nums = [1,1,1], k = 5→5
Constraints#
1 <= nums.length <= 10^5,1 <= k <= 10^15.
Approach#
Sliding window: maintain sum. Score is sum * (r - l + 1). Whenever score ≥ k, shrink. For each right, add r - l + 1 valid starting positions.
Solution#
class Solution {public: long long countSubarrays(vector<int>& nums, long long k) { long long sum = 0, ans = 0; int left = 0; for (int right = 0; right < (int)nums.size(); ++right) { sum += nums[right]; while (sum * (right - left + 1) >= k) { sum -= nums[left++]; } ans += right - left + 1; } return ans; }};func countSubarrays(nums []int, k int64) int64 { var sum, ans int64 left := 0 for right := 0; right < len(nums); right++ { sum += int64(nums[right]) for sum*int64(right-left+1) >= k { sum -= int64(nums[left]) left++ } ans += int64(right - left + 1) } return ans}from typing import List
class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: total = 0 ans = 0 left = 0 for right in range(len(nums)): total += nums[right] while total * (right - left + 1) >= k: total -= nums[left] left += 1 ans += right - left + 1 return ansfunction countSubarrays(nums, k) { let sum = 0n, ans = 0n; const kb = BigInt(k); let left = 0; for (let right = 0; right < nums.length; right++) { sum += BigInt(nums[right]); while (sum * BigInt(right - left + 1) >= kb) { sum -= BigInt(nums[left]); left++; } ans += BigInt(right - left + 1); } return Number(ans);}class Solution { public long countSubarrays(int[] nums, long k) { long sum = 0, ans = 0; int left = 0; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum * (right - left + 1) >= k) { sum -= nums[left++]; } ans += right - left + 1; } return ans; }}function countSubarrays(nums: number[], k: number): number { let sum = 0n, ans = 0n; const kb = BigInt(k); let left = 0; for (let right = 0; right < nums.length; right++) { sum += BigInt(nums[right]); while (sum * BigInt(right - left + 1) >= kb) { sum -= BigInt(nums[left]); left++; } ans += BigInt(right - left + 1); } return Number(ans);}Editorial#
Positivity is what makes the score monotone in window length for a fixed left, allowing a clean sliding window. With negatives, score isn’t monotone and we’d need a different structure. Each pointer advances at most n times → O(n).
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#