Count Subarrays With Score Less Than K — Problem & Solution
Count Subarrays With Score Less Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Subarrays With Score Less Than K is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The score of an array is the sum of its elements multiplied by its length. For example, the score of [1,2,3,4,5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.
Given an array nums of positive integers and an integer k, return the number of non-empty contiguous subarrays of nums whose score is strictly less than k.
CodeKairo note: the original problem allows k up to 10^15 and returns a 64-bit count; here nums.length and k are bounded so the answer fits in a 32-bit integer. Intermediate scores can still exceed 32 bits — compute them in 64-bit.
Example 1
Input: nums = [3,1,5,2], k = 12
Output: 5
Explanation: The four single elements plus `[3,1]` (score 8). `[1,5]` scores exactly 12, which is not less than 12.
Example 2
Input: nums = [1,2,1,2], k = 7
Output: 7
Explanation: Four singles and the three pairs (each score 6); every triple scores at least 12.
Example 3
Input: nums = [10], k = 10
Output: 0
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^51 <= k <= 10^9
Hints for Count Subarrays With Score Less Than K
Hint 1
All values are positive, so extending a subarray only increases its score, and shrinking it only decreases it.
Hint 2
For each right end, the valid left ends form a suffix ending at that right end. Find the smallest valid left end.
Hint 3
Slide a window: add
nums[right], then drop elements from the left whilesum * length >= k. Every window ending atrightthat starts at or afterleftis valid, so addright - left + 1.
How to solve Count Subarrays With Score Less Than K
Because every element is positive, the score is monotone under extension: a valid subarray stays valid when you shrink it. So for each right end there is a smallest valid left end, and it never moves backwards — a classic sliding window.
Approach
- Keep
left = 0, a runningsumand an answerans = 0. - For each
right, addnums[right]tosum. - While
sum * (right - left + 1) >= k, subtractnums[left]and advanceleft. - Now every subarray
[l, right]withleft <= l <= righthas score belowk; addright - left + 1toans.
Why it works
If [left, right] has score below k, then any [l, right] with l > left has a smaller sum and a smaller length, so a smaller score. If [left, right] is too big, then [left, right + 1] is too big as well, so left never needs to move back. Each element enters and leaves the window once, and for every right end we count exactly the valid left ends.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
sum * lengthcan reach about 5·10^13 — use 64-bit arithmetic.- The comparison is strict: a score equal to
kdoes not count. - When the window empties (
left > right), the score is 0, which is belowkbecausek >= 1, so the shrinking loop always stops.
Reference solution
Python
from typing import List
def countSubarrays(nums: List[int], k: int) -> int:
total = 0
left = 0
ans = 0
for right, v in enumerate(nums):
total += v
while total * (right - left + 1) >= k:
total -= nums[left]
left += 1
ans += right - left + 1
return ansJava
public static int countSubarrays(int[] nums, int 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];
left++;
}
ans += right - left + 1;
}
return (int) ans;
}C++
int countSubarrays(vector<int>& nums, int 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];
left++;
}
ans += right - left + 1;
}
return (int) ans;
}JavaScript
var countSubarrays = function(nums, k) {
var sum = 0, left = 0, ans = 0;
for (var right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum * (right - left + 1) >= k) {
sum -= nums[left];
left++;
}
ans += right - left + 1;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search