2302. Subarray Scores

Count Subarrays With Score Less Than K

I'll be honest: when I first saw this problem, I was worried. About what? Worried that in this strictly positive integer array of length $n$,

for some subarray $nums[i: j + 1]$ with $i < j < n$,

the addition of $nums[j + 1]$ could somehow cause $\text{sum}(nums[i: j + 2]) \times (j + 2 - i) < k$ to hold,

forcing my left-to-right traversal to occasionally look back and handle cases where subarray score suddenly drops.

But then...

Would That Actually Happen in This Problem? 🤔

Input array contains only natural numbers. This means: given a left index $i$,

if right index $j$ causes $\text{sum}(nums[i: j + 1]) \times (j + 1 - i) \geq k$,

then any further right index $l$ will also cause $\text{sum}(nums[i: l + 1]) \times (l + 1 - i) \geq k$,

and by an even larger margin. So the earlier worry was for a joke at all 🤣

Great! Let's Go Straight to It

We confidently adopt this strategy: once $\text{sum}(nums[i: j + 1]) \times (j + 1 - i) \geq k$,

keep incrementing $i$ until $\text{sum}(nums[i: j + 1]) \times (j + 1 - i) < k$ finally holds, or $i > j$.

Resulting values of $i$ and $j$ tell us: among subarrays with right boundary at index $j$,

exactly $j + 1 - i$ of them satisfy the constraint on $k$.

For each $j$, $i$ can go as far as $j + 1$, giving $j + 1 - i = 0$, meaning that

no subarray with right boundary at index $j$ satisfies our constraint.

As for why... see the follow-up problem section below.

Always Connect New Problems to Similar Solutions You've Written

⬆️ The approach here is identical to problem 2398. In fact, it's a simplified version.

Problem 2398 requires tracking window maximum, whereas problem 2302 doesn't ~~

So we save that $O(n)$ space which would've been needed for a monotonic decreasing deque, using just two pointers for sliding window's left and right ends,

plus a variable subarraySum to track $\text{sum}(nums[i: j + 1])$.

Simplified down to just $O(1)$ space ~~ Time complexity remains linear $O(n)$.

What If the Input Has Both Positive and Negative Numbers?

Algo Monster uses binary search for problem 2302, which handles the case where input contains both positive and negative numbers,

at the cost of $O(n \log n)$ time and $O(n)$ space.

Reading Problem Carefully Matters. Remember Bayes' Theorem

If we only knew input contains integers but not whether they're positive or negative,

we'd only have prior probability $P(Y)$ and would need to use more cumbersome binary search as Algo Monster did.

But the problem states clearly: only natural numbers are given. This is likelihood $P(X | Y)$ in hand.

So why not multiply it with prior to approach posterior $P(Y | X)$ and make a better judgment?

In a live coding interview, clarifying boundary constraints upfront is an essential skill.

A favor to both the interviewer and yourself.

That's exactly what I did for problem 2302 — reducing complexity from Algo Monster's $O(n \log n)$ time and $O(n)$ space down to $O(n)$ and $O(1)$.

C++

#include <vector>
using namespace std;

long long countSubarrayScores(vector<int>& nums, long long k) // LeetCode Q.2302.
{
    long long lessThanKSubarraysCount = 0; // Long long prevents overflow.

    long long subarraySum = 0; // Long long prevents overflow.

    int leftIdx = 0;
    for (int rightIdx = 0; rightIdx < nums.size(); rightIdx++) {
        subarraySum += nums[rightIdx];

        while (subarraySum * (rightIdx + 1 - leftIdx) >= k) {
            subarraySum -= nums[leftIdx];
            leftIdx++;
        }

        lessThanKSubarraysCount += rightIdx + 1 - leftIdx;
    }

    return lessThanKSubarraysCount;
}

Python

def count_subarray_scores(nums: list[int], k: int) -> int:  # LeetCode Q.2302.
    total_subarrays = 0
    subarray_sum = 0

    start_idx = 0
    for end_idx, num in enumerate(nums):
        subarray_sum += nums[end_idx]
        score = subarray_sum * (end_idx + 1 - start_idx)

        while score >= k and start_idx <= end_idx:
            subarray_sum -= nums[start_idx]
            start_idx += 1
            score = subarray_sum * (end_idx + 1 - start_idx)

        total_subarrays += end_idx + 1 - start_idx

    return total_subarrays

Follow-up Problem

When scanning subarrays with right boundary at index $j$, if the left boundary $i$ increments all the way to $j + 1$, what conclusion can we draw about $nums[j]$?