Count Subarrays With Score Less Than K

Count subarrays where (sum × length) < k, using a sliding window over positive integers.

Hard
Time O(n) Space O(1)
LeetCode
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 = 106
  • nums = [1,1,1], k = 55

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#

Count Subarrays With Score Less Than K
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.