#2302

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Count Subarrays With Score Less Than K

Count all non-empty subarrays whose score, defined as sum times length, is strictly less than a given integer k efficiently.

array binary search sliding window prefix sum

Problem Statement

You are given an array of positive integers nums and an integer k. The score of a subarray is defined as the product of its sum and its length. Determine how many non-empty contiguous subarrays have a score strictly less than k.

A subarray is any contiguous portion of nums. For example, [nums[i], nums[i+1], ..., nums[j]] counts if its sum multiplied by its length is less than k. Return the total number of such subarrays.

Examples

Example 1

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

Output: 6

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

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

Solution Approach

Binary Search Over Valid Lengths

Use binary search to find the maximum length for subarrays starting at each index whose score remains under k. This leverages the pattern of narrowing the answer space without enumerating every subarray.

Sliding Window With Prefix Sums

Maintain a running sum using a sliding window or prefix sum array. Incrementally add elements and check if extending the window exceeds the score threshold, which efficiently counts valid subarrays starting at each index.

Handle Edge Cases and Single Elements

Every single element subarray must be checked individually. Pay attention to cases where the score equals or exceeds k immediately to avoid off-by-one errors, especially with large k values or small arrays.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each element is processed at most twice in the sliding window. Space complexity is O(1) additional space beyond the input array if prefix sums are maintained in place.

What Interviewers Usually Probe

Look for binary search usage on the maximum valid length to see if the candidate recognizes the answer-space pattern.
Observe if the candidate optimizes with sliding window rather than brute-force O(n^2) subarray enumeration.
Check for careful handling of single-element subarrays and edge score thresholds to avoid off-by-one mistakes.

Common Pitfalls or Variants

Common pitfalls

Brute-force enumeration of all subarrays leads to TLE for large arrays; always consider binary search or prefix sum optimization.
Failing to account for single-element subarrays can cause undercounting.
Incorrectly updating sum or length in sliding window may miscount subarrays crossing the threshold exactly at k.

Follow-up variants

Count subarrays with sum less than k ignoring the length multiplier.
Find maximum length subarray with score less than k instead of counting all.
Return subarrays themselves rather than counts, applying the same binary search check.

FAQ

What is the best pattern to solve Count Subarrays With Score Less Than K?

Binary search over the valid answer space combined with sliding window is the recommended pattern for this problem.

Can I use brute force to count subarrays?

Brute force works only for small arrays; for larger arrays it will exceed time limits due to O(n^2) complexity.

Do I need to consider single-element subarrays?

Yes, each single element forms a valid subarray and must be counted if its score is less than k.

How does the sliding window help in this problem?

Sliding window efficiently maintains running sums to check score constraints without recomputing subarray sums repeatedly.

What is a common mistake with binary search here?

A common mistake is off-by-one errors when determining maximum subarray length that keeps the score strictly less than k.

terminal

Solution

Solution 1: Prefix Sum + Binary Search

First, we calculate the prefix sum array $s$ of the array $\textit{nums}$, where $s[i]$ represents the sum of the first $i$ elements of $\textit{nums}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)):
            l, r = 0, i
            while l < r:
                mid = (l + r + 1) >> 1
                if (s[i] - s[i - mid]) * mid < k:
                    l = mid
                else:
                    r = mid - 1
            ans += l
        return ans

Solution 2: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)):
            l, r = 0, i
            while l < r:
                mid = (l + r + 1) >> 1
                if (s[i] - s[i - mid]) * mid < k:
                    l = mid
                else:
                    r = mid - 1
            ans += l
        return ans

Continue Practicing

#2271 maximum white tiles covered by a carpet #2398 maximum number of robots within budget #2106 maximum fruits harvested after at most k steps