Solution: Count Subarrays With Score Less Than K

Statement

An array score is defined as the sum of the array elements multiplied by its length. For example, if the array is $[2, 1, 5]$, then its score is $(2 + 1 + 5) \times 3$ = $24$.

Given an array of positive integers, nums, and a positive integer k, count and return the number of non-empty subarrays of nums whose score is strictly less than k.

Note: A subarray is a contiguous sequence of elements within an array.

Constraints:

• $1 \leq$ nums.length $\leq 10^{3}$

• $1 \leq$ nums[i] $\leq 10^{3}$

• $1 \leq$ k $\leq 10^{5}$

Solution

A straightforward way to solve this would be to look at every possible subarray of nums, calculate its score, and check if it's less than k. If nums has n elements, there are $\frac{n(n+1)}{2n}$ possible subarrays. Checking those individually will be very slow and inefficient, specifically when n becomes large.

Instead of recalculating the sum and score for every possible subarray, a sliding window approach can achieve the result in a single pass. The idea is to maintain a window using two pointers and keep track of a running sumThe running sum is the total sum of all elements present within the sliding window (i.e., the subarray formed by it). It is updated as the window expands or shrinks. while moving through the array. Start with both pointers at the beginning of the array. The right pointer expands the window by moving forward, while the left pointer adjusts the start of the window when needed. Each time a new element is added, we update the running sum and compute the subarray’s score as:

$current ~score$ = $current~running~sum ~\times ~length~of~the ~subarray$

If the score is less than k, then not only is the current subarray valid, but all subarrays ending at the current right pointer and starting anywhere within the window are also valid. If the entire window from the left to the right pointer has a valid score, any shorter subarray within that window (as long as it still ends at the right pointer position) will also have a valid score. For example, if the subarray [nums[i], ..., nums[j]] is valid, then the subarray [nums[i+1], ..., nums[j]] is also valid (it’s shorter, so its score will be even smaller or the same, and less than k). The same logic applies to the subarray [nums[i+2], ..., nums[j]], [nums[i+3], ..., nums[j]], and so on. The count of all such valid subarrays within a subarray can be calculated as:

$all~valid~subarrays$ = $right ~index ~-~ left ~index ~+~ 1$

If the score exceeds or equals k, shrink the window from the left by moving the left pointer forward and updating the running sum accordingly. This continues until the current window/subarray score drops below k.

By repeating this process throughout the array, i.e., expanding the second pointer and adjusting the first, the algorithm counts all valid subarrays efficiently, without checking each one individually.

Let's look at the algorithm steps:

1. Initialize the variables:

   1. Set result = 0 to accumulate the total count of valid subarrays.

   2. Set runningSum = 0 to keep a running sum of elements in the current window.

   3. Set left = 0 as the start index of the sliding window.

2. Use the right pointer to iterate over the nums list. In each iteration:

   1. Add the number at nums[right] to runningSum. This effectively expands the window to the right.

   2. Compute the current window’s score as score = runningSum * (right - left + 1). Here, (right - left + 1) is the window’s length. Multiplying by runningSum gives the score of the subarray from left to right.

   3. If the score exceeds k, shrink the window. While score >= k:

      1. Subtract the number at nums[left] from runningSum. This removes the leftmost element from the window.

      2. Increment left by 1. This moves the left boundary of the window to the right.

      3. Recompute the score as both runningSum and window length have changed.

   4. Once the score is less than k, count all valid subarrays ending at right, i.e., add (right - left + 1) to the result.

3. Once the entire nums list has been traversed, return the result with the total number of subarrays whose score is less than k.

The slides below help to understand the solution in a better way.