Count Subarrays With Score Less Than K solution and explanation
Google
9 more videos on this problem
Count Subarrays With Score Less Than K | Leetcode 2302Techdose · 19:28 · 3K views
2302. Count Subarrays With Score Less Than K (Leetcode Hard)Programming Live with Larry · 12:40 · 1K views
LeetCode 2302 Count Subarrays With Score Less Than K | Hard ➡️ Medium | Sliding Window | GoogleCode Harmony · 27:10 · 347 views
Leetcode 2302. Count Subarrays With Score Less Than K - two-pointer sliding window methodCode-Yao · 16:09 · 178 views
LeetCode 2302 - Count Subarrays With Score Less Than K - PythonAlpha-Code · 6:14 · 142 views
2302. Count Subarrays With Score Less Than K | Leetcode Daily - PythonLeetcode Daily · 9:34 · 133 views
Count Subarrays With Score Less Than K | LeetCode 2302 | Sliding Window | Java | Developer CoderDeveloper Coder · 13:49 · 78 views
Count Subarrays With Score Less Than K - Leetcode 2302 - PythonTim Huang · 4:24 · 72 views
2302. Count Subarrays With Score Less Than K | Java | Leetcode |JavAttack · 3:44 · 53 views
2302. Count Subarrays With Score Less Than K | POTD | April 28th, 2025Tech Courses · 10:09 · 52 views
The problem
The score of an array is defined as the product of its sum and its length.
- For example, the score of
[1, 2, 3, 4, 5]is(1 + 2 + 3 + 4 + 5) * 5 = 75.
Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [2,1,4,3,5], k = 10 Output: 6 Explanation: The 6 subarrays having scores less than 10 are: - [2] with score 2 * 1 = 2. - [1] with score 1 * 1 = 1. - [4] with score 4 * 1 = 4. - [3] with score 3 * 1 = 3. - [5] with score 5 * 1 = 5. - [2,1] with score (2 + 1) * 2 = 6. Note that subarrays such as [1,4] and [4,3,5] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10.
Example 2:
Input: nums = [1,1,1], k = 5 Output: 5 Explanation: Every subarray except [1,1,1] has a score less than 5. [1,1,1] has a score (1 + 1 + 1) * 3 = 9, which is greater than 5. Thus, there are 5 subarrays having scores less than 5.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= 1015
Approach overview
Problem Overview: Given an array nums and an integer k, count the number of contiguous subarrays where score = sum(subarray) * length(subarray) is strictly less than k. The challenge is evaluating many subarrays efficiently without recomputing sums repeatedly.
Approach 1: Sliding Window Method (O(n) time, O(1) space)
This is the optimal solution. Maintain a window with two pointers left and right while tracking the running sum of the current window. As you extend the window by moving right, update the sum and check whether sum * window_length is still less than k. If the score becomes too large, move left forward and subtract values from the sum until the constraint holds again. For every valid right, all subarrays ending at that index and starting between left and right are valid, so add right - left + 1 to the answer. Each element enters and leaves the window at most once, giving linear time complexity. This technique is a classic application of the sliding window pattern on positive arrays.
Approach 2: Prefix Sum and Binary Search (O(n log n) time, O(n) space)
Precompute a prefix array where prefix[i] stores the sum of the first i elements. For each starting index i, you want the largest ending index j such that (prefix[j] - prefix[i]) * (j - i) < k. Because the prefix sum is monotonic when numbers are positive, you can binary search the maximum valid j. This approach separates sum computation using prefix sums and boundary search using binary search. It is slightly slower than sliding window but still efficient and easier to reason about if you prefer explicit range queries.
Recommended for interviews: The sliding window approach is the expected solution. It demonstrates recognition of monotonic constraints and efficient two‑pointer window expansion. The prefix sum + binary search variant shows deeper algorithmic thinking but is rarely required once you realize the window can shrink dynamically.
Approach 1: Sliding Window Method
The sliding window method allows us to efficiently find subarrays with a score less than k by maintaining a running sum and adjusting the window size dynamically. By expanding and contracting the window, we can iterate through the array in linear time.
def count_subarrays(nums, k):
sum_ = 0
count = 0
left = 0
for right in range(len(nums)):
sum_ += nums[right]
while sum_ * (right - left + 1) >= k:
sum_ -= nums[left]
left += 1
count += (right - left + 1)
return count
nums = [2, 1, 4, 3, 5]
k = 10
print(count_subarrays(nums, k))public class Solution {
public int countSubarrays(int[] nums, long k) {
long sum = 0;
int count = 0, left = 0;
for (int right = 0; right < nums.length; ++right) {
sum += nums[right];
while (sum * (right - left + 1) >= k) {
sum -= nums[left++];
}
count += (right - left + 1);
}
return count;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 1, 4, 3, 5};
long k = 10;
System.out.println(solution.countSubarrays(nums, k));
}
}#include <vector>
int countSubarrays(std::vector<int>& nums, long long k) {
long long sum = 0;
int count = 0, left = 0;
for (int right = 0; right < nums.size(); ++right) {
sum += nums[right];
while (sum * (right - left + 1) >= k) {
sum -= nums[left++];
}
count += (right - left + 1);
}
return count;
}
int main() {
std::vector<int> nums = {2, 1, 4, 3, 5};
int k = 10;
int result = countSubarrays(nums, k);
std::cout << result << std::endl;
return 0;
}function countSubarrays(nums, k) {
let sum = 0;
let count = 0;
let left = 0;
for (let right = 0; right < nums.length; ++right) {
sum += nums[right];
while (sum * (right - left + 1) >= k) {
sum -= nums[left++];
}
count += (right - left + 1);
}
return count;
}
let nums = [2, 1, 4, 3, 5];
let k = 10;
console.log(countSubarrays(nums, k));#include <stdio.h>
int countSubarrays(int* nums, int numsSize, long long k) {
long long sum = 0;
int count = 0, left = 0;
for (int right = 0; right < numsSize; ++right) {
sum += nums[right];
while (sum * (right - left + 1) >= k) {
sum -= nums[left++];
}
count += (right - left + 1);
}
return count;
}
int main() {
int nums[] = {2, 1, 4, 3, 5};
int k = 10;
int result = countSubarrays(nums, 5, k);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int CountSubarrays(int[] nums, long k) {
long sum = 0;
int count = 0, left = 0;
for (int right = 0; right < nums.Length; ++right) {
sum += nums[right];
while (sum * (right - left + 1) >= k) {
sum -= nums[left++];
}
count += (right - left + 1);
}
return count;
}
static void Main() {
int[] nums = {2, 1, 4, 3, 5};
long k = 10;
Console.WriteLine(CountSubarrays(nums, k));
}
}This Python solution approaches the problem using a sliding window pattern. The running sum is maintained, and the pointers adjust to ensure the subarray score remains less than k. Valid subarrays are counted as the window moves across the array.
Time Complexity: O(n), where n is the length of the input list.
Space Complexity: O(1), as the space used does not grow with input size.
Approach 2: Prefix Sum and Binary Search
This alternative method utilizes prefix sums to preprocess the array, enabling efficient calculation of subarray sums. By combining this with binary search, it's possible to find valid subarrays more explicitly.
def count_subarrays(nums, k):
prefix_sums = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefix_sums[i + 1] = prefix_sums[i] + nums[i]
count = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
if (prefix_sums[j + 1] - prefix_sums[i]) * (j - i + 1) < k:
count += 1
else:
break
return count
nums = [2, 1, 4, 3, 5]
k = 10
print(count_subarrays(nums, k))public class Solution {
public int countSubarrays(int[] nums, long k) {
long[] prefixSums = new long[nums.length + 1];
for (int i = 0; i < nums.length; ++i) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int count = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i; j < nums.length; ++j) {
if ((prefixSums[j + 1] - prefixSums[i]) * (j - i + 1) < k) {
count++;
} else {
break;
}
}
}
return count;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 1, 4, 3, 5};
long k = 10;
System.out.println(solution.countSubarrays(nums, k));
}
}#include <vector>
int countSubarrays(std::vector<int>& nums, long long k) {
std::vector<long long> prefixSums(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); ++i) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int count = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i; j < nums.size(); ++j) {
if ((prefixSums[j + 1] - prefixSums[i]) * (j - i + 1) < k) {
count++;
} else {
break;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {2, 1, 4, 3, 5};
long long k = 10;
int result = countSubarrays(nums, k);
std::cout << result << std::endl;
return 0;
}function countSubarrays(nums, k) {
let prefixSums = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
if ((prefixSums[j + 1] - prefixSums[i]) * (j - i + 1) < k) {
count++;
} else {
break;
}
}
}
return count;
}
let nums = [2, 1, 4, 3, 5];
let k = 10;
console.log(countSubarrays(nums, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int countSubarrays(int* nums, int numsSize, long long k) {
long long* prefixSums = (long long*)malloc((numsSize + 1) * sizeof(long long));
prefixSums[0] = 0;
for (int i = 0; i < numsSize; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i; j < numsSize; j++) {
if ((prefixSums[j + 1] - prefixSums[i]) * (j - i + 1) < k) {
count++;
} else {
break;
}
}
}
free(prefixSums);
return count;
}
int main() {
int nums[] = {2, 1, 4, 3, 5};
int k = 10;
int result = countSubarrays(nums, 5, k);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int CountSubarrays(int[] nums, long k) {
long[] prefixSums = new long[nums.Length + 1];
for (int i = 0; i < nums.Length; ++i) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int count = 0;
for (int i = 0; i < nums.Length; ++i) {
for (int j = i; j < nums.Length; ++j) {
if ((prefixSums[j + 1] - prefixSums[i]) * (j - i + 1) < k) {
count++;
} else {
break;
}
}
}
return count;
}
static void Main() {
int[] nums = {2, 1, 4, 3, 5};
long k = 10;
Console.WriteLine(CountSubarrays(nums, k));
}
}This Python approach computes prefix sums to check subarray scores, leveraging the precomputed sums to verify the conditions for valid subarray count in nested loops.
Time Complexity: O(n^2), due to subarray evaluations.
Space Complexity: O(n), for storing prefix sums.
Approach 3: Prefix Sum + Binary Search
First, we calculate the prefix sum array s of the array nums, where s[i] represents the sum of the first i elements of nums.
Next, we enumerate each element of nums as the last element of a subarray. For each element, we can use binary search to find the maximum length l such that s[i] - s[i - l] times l < k. The number of subarrays ending at this element is l, and summing up all l gives the final answer.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
function countSubarrays(nums: number[], k: number): number {
const n = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
let ans = 0;
for (let i = 1; i <= n; ++i) {
let [l, r] = [0, i];
while (l < r) {
const mid = (l + r + 1) >> 1;
if ((s[i] - s[i - mid]) * mid < k) {
l = mid;
} else {
r = mid - 1;
}
}
ans += l;
}
return ans;
}func countSubarrays(nums []int, k int64) (ans int64) {
n := len(nums)
s := make([]int64, n+1)
for i, x := range nums {
s[i+1] = s[i] + int64(x)
}
for i := 1; i <= n; i++ {
l, r := 0, i
for l < r {
mid := (l + r + 1) >> 1
if (s[i]-s[i-mid])*int64(mid) < k {
l = mid
} else {
r = mid - 1
}
}
ans += int64(l)
}
return
}impl Solution {
pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
let n = nums.len();
let mut s = vec![0i64; n + 1];
for i in 0..n {
s[i + 1] = s[i] + nums[i] as i64;
}
let mut ans = 0i64;
for i in 1..=n {
let mut l = 0;
let mut r = i;
while l < r {
let mid = (l + r + 1) / 2;
let sum = s[i] - s[i - mid];
if sum * (mid as i64) < k {
l = mid;
} else {
r = mid - 1;
}
}
ans += l as i64;
}
ans
}
}Approach 4: Two Pointers
We can use the two-pointer technique to maintain a sliding window such that the sum of elements in the window is less than k. The number of subarrays ending at the current element is equal to the length of the window. Summing up all the window lengths gives the final answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function countSubarrays(nums: number[], k: number): number {
let [ans, s, j] = [0, 0, 0];
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
while (s * (i - j + 1) >= k) {
s -= nums[j++];
}
ans += i - j + 1;
}
return ans;
}func countSubarrays(nums []int, k int64) (ans int64) {
s, j := 0, 0
for i, x := range nums {
s += x
for int64(s*(i-j+1)) >= k {
s -= nums[j]
j++
}
ans += int64(i - j + 1)
}
return
}impl Solution {
pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
let mut ans = 0i64;
let mut s = 0i64;
let mut j = 0;
for i in 0..nums.len() {
s += nums[i] as i64;
while s * (i as i64 - j as i64 + 1) >= k {
s -= nums[j] as i64;
j += 1;
}
ans += i as i64 - j as i64 + 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Method | Time Complexity: O(n), where n is the length of the input list. |
| Prefix Sum and Binary Search | Time Complexity: O(n^2), due to subarray evaluations. |
| Prefix Sum + Binary Search | – |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution when array values are positive and window can shrink dynamically |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Useful when you want explicit range sums and search for the maximum valid end index |
Frequently asked questions
Is Count Subarrays With Score Less Than K easy or hard?
The problem is labeled Hard on LeetCode because the score formula combines both sum and length, which can confuse brute force attempts. Once the sliding window observation is recognized, the implementation becomes relatively straightforward with linear time complexity.
Count Subarrays With Score Less Than K Python/Java solution
Most implementations follow the same sliding window logic across languages. Maintain two pointers and a running sum, expand the window with the right pointer, and shrink from the left when the score constraint fails. The algorithm runs in O(n) time and is straightforward to implement in Python, Java, C++, and other languages.
How to solve Count Subarrays With Score Less Than K in O(n)?
Use a sliding window with two pointers and maintain the running sum of the current subarray. Expand the right pointer, and while (sum * window_length) becomes greater than or equal to k, move the left pointer forward to shrink the window. For each right index, add the number of valid subarrays ending there, which is right - left + 1.
What is the best approach for Count Subarrays With Score Less Than K?
The sliding window approach is the most efficient method. It maintains a running sum and dynamically adjusts the left boundary while expanding the right pointer. Each element is processed at most twice, resulting in O(n) time and O(1) extra space.
Is Count Subarrays With Score Less Than K asked at Google/Amazon/Meta?
Variants of sliding window and subarray counting problems frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of two‑pointer techniques, prefix sums, and reasoning about subarray constraints.
What data structure is used in Count Subarrays With Score Less Than K?
The main technique uses the sliding window pattern with two pointers and a running sum variable. The alternative approach uses a prefix sum array combined with binary search to efficiently compute subarray sums and locate valid boundaries.
What is the time complexity of Count Subarrays With Score Less Than K?
The optimal sliding window solution runs in O(n) time because each element enters and leaves the window at most once. An alternative prefix sum with binary search approach runs in O(n log n) time due to the binary search for every starting index.