# Count Subarrays With Score Less Than K
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-subarrays-with-score-less-than-k)
Canonical: https://scaleengineer.com/dsa/problems/count-subarrays-with-score-less-than-k
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## 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 <= 105`
* `1 <= nums[i] <= 105`
* `1 <= k <= 1015`

# Approaches
## Brute Force with Nested Loops
This approach involves checking every possible non-empty subarray. For each subarray, we calculate its score, which is the product of its sum and length. If the score is less than the given value `k`, we increment a counter. This method is straightforward but inefficient for large inputs.
**Time:** O(n^2), where n is the number of elements in `nums`. The nested loops lead to a quadratic number of operations in the worst case. · **Space:** O(1), as we only use a few variables to store the count, sum, and loop indices, regardless of the input size.
**Pros:** Simple to understand and implement.; Guaranteed to be correct if implemented properly.
**Cons:** Highly inefficient with a time complexity of O(n^2).; Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
### Explanation
The algorithm uses two nested loops to generate all subarrays. The outer loop fixes the starting index `i`, and the inner loop iterates through all possible ending indices `j` from `i` onwards.

To optimize the calculation of the sum for each subarray `nums[i..j]`, we maintain a running sum. For a fixed `i`, as `j` increases, we simply add `nums[j]` to the sum of the previous subarray `nums[i..j-1]`. The length of the subarray is `j - i + 1`.

The score is then `(running sum) * (length)`. If this score is strictly less than `k`, we increment our total count. A small optimization is added: if a subarray's score meets or exceeds `k`, we can stop extending it (break the inner loop), because any longer subarray starting at the same index `i` will have an even larger score, as all numbers are positive.

Due to the potential for large sums and scores (up to 10<sup>15</sup>), it's crucial to use a 64-bit integer type (like `long` in Java) for the sum, score, and count variables to prevent overflow.

```java
class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            long currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                long length = j - i + 1;
                if (currentSum * length < k) {
                    count++;
                } else {
                    // Since all numbers are positive, if the score for nums[i..j]
                    // is >= k, the score for any longer subarray starting at i
                    // will also be >= k. We can break the inner loop.
                    break; 
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Loop through the array with an index `i` from 0 to `n-1` to serve as the start of the subarray.
- Inside this loop, initialize `currentSum = 0L`.
- Start a nested loop with an index `j` from `i` to `n-1` to serve as the end of the subarray.
- Add `nums[j]` to `currentSum`.
- Calculate the subarray's score: `score = currentSum * (j - i + 1)`.
- If `score < k`, increment `count`.
- If `score >= k`, break the inner loop as further extensions of the subarray will also have scores `>= k`.
- After the loops complete, return `count`.

## Optimal Sliding Window
A much more efficient solution uses the sliding window technique. This approach maintains a 'window' (a subarray) and expands it to the right. If the window's score becomes too high, it shrinks the window from the left. The key insight is that if a window `[left, right]` is valid (score < k), then all subarrays ending at `right` that are contained within this window are also valid. This allows us to count valid subarrays in a single pass.
**Time:** O(n), where n is the number of elements in `nums`. Each pointer, `left` and `right`, traverses the array at most once, leading to linear time performance. · **Space:** O(1), as it only requires a few variables for the pointers, sum, and count, independent of the input size.
**Pros:** Extremely efficient with O(n) time complexity.; Optimal solution for the given problem constraints.; Uses constant extra space.
**Cons:** The logic can be less intuitive than the straightforward brute-force approach.
### Explanation
We use two pointers, `left` and `right`, to represent the current window `[left, right]`. We iterate `right` from the beginning to the end of the array to expand the window.

1. Initialize `left = 0`, `currentSum = 0`, and `count = 0`.
2. Loop with `right` from `0` to `n-1`:
   a. Add `nums[right]` to `currentSum`.
   b. Check the score of the current window `[left, right]`: `score = currentSum * (right - left + 1)`.
   c. While `score >= k`, the window is invalid. We shrink it by removing the leftmost element: subtract `nums[left]` from `currentSum` and increment `left`.
3. After the `while` loop, `left` is the earliest possible start for a valid subarray ending at `right`.
4. All subarrays `[i, right]` where `left <= i <= right` are valid. The number of such subarrays is `right - left + 1`. We add this to our total `count`.
5. This process is repeated for all `right`, and the final `count` is the answer. Using `long` for `currentSum` and `count` is essential to avoid overflow.

```java
class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0;
        long currentSum = 0;
        int left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            
            while (currentSum * (right - left + 1) >= k) {
                currentSum -= nums[left];
                left++;
            }
            
            count += (right - left + 1);
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0L`, `currentSum = 0L`, and `left = 0`.
- Iterate through the array with a `right` pointer from 0 to `n-1`.
- Add `nums[right]` to `currentSum`.
- While the score of the window `[left, right]`, calculated as `currentSum * (right - left + 1)`, is greater than or equal to `k`:
    - Subtract `nums[left]` from `currentSum`.
    - Increment `left`.
- The number of valid subarrays ending at `right` is `right - left + 1`. Add this to `count`.
- After the loop, return `count`.

# Solutions
### Java

```java
class Solution { public long countSubarrays ( int [] nums , long k ) { int n = nums . length ; long [] s = new long [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } long ans = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int left = 0 , right = i ; while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if (( s [ i ] - s [ i - mid ]) * mid < k ) { left = mid ; } else { right = mid - 1 ; } } ans += left ; } return ans ; } }
```

### CPP

```cpp
class Solution { public: long long countSubarrays ( vector < int >& nums , long long k ) { int n = nums . size (); long long s [ n + 1 ]; s [ 0 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } long long ans = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int left = 0 , right = i ; while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if (( s [ i ] - s [ i - mid ]) * mid < k ) { left = mid ; } else { right = mid - 1 ; } } ans += left ; } return ans ; } };
```

### Python

```python
class Solution : def countSubarrays ( self , nums : List [ int ], k : int ) -> int : s = list ( accumulate ( nums , initial = 0 )) ans = 0 for i in range ( 1 , len ( s )): left , right = 0 , i while left < right : mid = ( left + right + 1 ) >> 1 if ( s [ i ] - s [ i - mid ]) * mid < k : left = mid else : right = mid - 1 ans += left return ans
```