Count Subarrays Where Score Is Less Than K — Shrinkable Window [LC 2302, Google]

Problem Statement#

LeetCode 2302 — Count Subarrays Where Score Is Less Than K · Difficulty: Hard

The score of an array is defined as the product of its sum and its length. Given a positive integer array nums and a positive integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= k <= 10^15

Example 1:

Input:  nums = [2, 1, 4, 3, 5], k = 10
Output: 6
Explanation: Subarrays with score < 10:
  [2]       score = 2×1 = 2  ✓
  [1]       score = 1×1 = 1  ✓
  [4]       score = 4×1 = 4  ✓
  [3]       score = 3×1 = 3  ✓
  [5]       score = 5×1 = 5  ✓
  [2,1]     score = 3×2 = 6  ✓
  [1,4]     score = 5×2 = 10 ✗
  ...
  6 subarrays total.

Example 2:

Input:  nums = [1, 1, 1], k = 5
Output: 5
Explanation: [1]×3 + [1,1]×2 + [1,1,1]×1 = 3+4+3 = ... check:
  [1]:3 have score 1; [1,1]:2 have score 2×2=4; [1,1,1]: 3×3=9 >= 5 ✗
  Valid: 3 + 2 = 5.

Why This Problem Matters#

LC 2302 is the textbook example of shrinkable window counting: instead of iterating over all O(n²) subarrays, we observe that if a window [left, right] has score >= k, we shrink it from the left until it is valid, and then all subarrays ending at right with left boundary in [left, right] are valid — exactly right - left + 1 of them.

All numbers are positive, so adding an element to the right always increases the score and removing from the left always decreases it. This monotonicity is what makes the shrinkable window work.

Google asks this problem to test whether candidates know the counting trick: "for each right, how many lefts give a valid subarray?" Once the window is shrunk to valid, the answer contribution is exactly right - left + 1.

The Core Insight#

Since all nums[i] >= 1, the score sum * length is monotone in window size: expanding the window can only increase or keep the score the same, and shrinking from the left can only decrease or keep it the same.

Algorithm:

1. Maintain a running sum and a left pointer.
2. For each right, add nums[right] to the sum.
3. While sum * (right - left + 1) >= k, remove nums[left] from the sum and advance left.
4. All right - left + 1 subarrays ending at right (with left boundaries from left to right) are valid. Add that count to the answer.

This single pass is O(n) because left only moves forward.

Visual Dry Run#

Input: nums = [2, 1, 4, 3, 5], k = 10

Total: 1+2+1+1+1 = 6 ✓

Common Mistakes#

1. Using >= k vs > k in the while condition. The problem asks for score strictly less than k. The window shrinks while score >= k. Using > k would leave invalid windows and overcount.

2. Overflow with sum * length. With nums[i] up to 10^5 and n up to 10^5, the maximum sum is 10^10 and the maximum score is 10^10 * 10^5 = 10^15 — which overflows a 32-bit integer. Use long long in C++ or Python (which handles big integers natively). In JavaScript, the numbers stay within the safe integer range because k <= 10^15 < 2^53.

3. Counting subarrays as right - left instead of right - left + 1. After shrinking, the valid left boundaries are left, left+1, ..., right — that is right - left + 1 boundaries, not right - left.

4. Breaking the loop early when left > right. This happens when a single element nums[right] * 1 >= k — the window is empty and contributes 0. This is handled correctly because right - left + 1 becomes 0 when left = right + 1.

5. Forgetting that k can be very large. Use 64-bit arithmetic throughout. In Python, no issue; in C++ declare k as long long; in JavaScript, standard number handles up to 2^53 ≈ 9×10^15, which covers k <= 10^15.

Solutions#

Python#

def countSubarrays(nums: list[int], k: int) -> int:
    left = 0
    running_sum = 0
    ans = 0
 
    for right in range(len(nums)):
        running_sum += nums[right]               # expand window right
 
        # Shrink from left while score >= k
        while running_sum * (right - left + 1) >= k:
            running_sum -= nums[left]            # remove leftmost element
            left += 1                            # advance left pointer
 
        # All subarrays [left..right], [left+1..right], ..., [right..right]
        # have score < k. There are (right - left + 1) of them.
        ans += right - left + 1
 
    return ans

JavaScript#

function countSubarrays(nums, k) {
    let left = 0;
    let runningSum = 0;
    let ans = 0;
 
    for (let right = 0; right < nums.length; right++) {
        runningSum += nums[right];               // expand: add right element
 
        // Shrink from left while score = sum * length >= k
        while (runningSum * (right - left + 1) >= k) {
            runningSum -= nums[left];            // remove leftmost element
            left++;                              // advance left pointer
        }
 
        // Count all valid subarrays ending at 'right'
        // Left boundaries can be left, left+1, ..., right → (right - left + 1) choices
        ans += right - left + 1;
    }
 
    return ans;
}

Complexity Analysis#

Each element is added to runningSum exactly once (when right passes it) and removed at most once (when left passes it). The total number of operations across all iterations of the while loop is at most n. Total: O(n) time, O(1) space.

Follow-up Questions#

1. What if nums can contain zeros? With zeros, the score can stay 0 regardless of length, so the window may grow unboundedly. The algorithm still works: if score < k, we never shrink, so every extension contributes right - left + 1 valid subarrays.

2. What if the score condition is score <= k (inclusive)? Change >= k to > k in the while condition. The rest of the algorithm is identical.

3. LC 713 (Subarray Product Less Than K): Same shrinkable window counting pattern, but with product instead of sum-times-length. The counting trick right - left + 1 is identical.

4. What if you need subarrays with score exactly k? Use atLeast(k) - atLeast(k+1) where atLeast(x) counts subarrays with score >= x. This "exactly equals" trick converts two shrinkable-window passes into the answer.

This Pattern Solves#

• LC 2302 — Count Subarrays Where Score Is Less Than K (this problem)
• LC 713 — Subarray Product Less Than K (product instead of sum×length)
• LC 904 — Fruit Into Baskets (count subarrays with at most 2 distinct values)
• LC 992 — Subarrays with K Different Integers (at-least minus at-least)
• LC 209 — Minimum Size Subarray Sum (minimize length instead of counting)

Key Takeaways#

• All elements are positive, so score sum * length is monotone in window size — this monotonicity is what makes a shrinkable window valid and correct.
• For each right, after shrinking, there are exactly right - left + 1 valid subarrays ending at right; add this count directly to the answer instead of iterating over left boundaries.
• Use 64-bit arithmetic: sum can reach 10^10 and score can reach 10^15 — 32-bit overflow is the most common silent bug in C++ solutions.
• The shrink condition is score >= k (strict: problem asks for score < k); use > k when the problem asks for score <= k.
• Both left and right advance at most n times total, giving O(n) time and O(1) space — optimal for this problem.
• The counting trick right - left + 1 is the same trick used in LC 713 (subarray product), LC 904 (at-most-k-distinct), and LC 992 (k-different) — learn it once, apply everywhere.
• Google asks this to verify that candidates can derive "how many subarrays are valid?" from a sliding window, not just "is this specific window valid?"