Count Subarrays With Score Less Than K

To solve the problem of counting the number of non-empty subarrays of nums whose score is strictly less than k, we can use a sliding window approach. We’ll keep track of the sum of elements in the current window and expand the window to the right until the score becomes greater or equal to k. Then, we’ll shrink the window from the left to find the next valid subarray.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        left = 0
        right = 0
        current_sum = 0
        count = 0

        # Iterate through the nums array
        while right < len(nums):
            # Add the current number to the current_sum
            current_sum += nums[right]

            # If the score of the current subarray is greater or equal to k, shrink the window from the left
            while current_sum * (right - left + 1) >= k:
                current_sum -= nums[left]
                left += 1

            # Increment the count by the length of the current window
            count += right - left + 1

            # Move the right pointer to the next element
            right += 1

        return count

Explanation:

Initialize Pointers: left and right pointers to define the current window and current_sum to store the sum of elements in the current window.
Expand Window: Move the right pointer to the next element, adding its value to current_sum.
Shrink Window: If the score of the current window (i.e., current_sum * (right - left + 1)) is greater or equal to k, shrink the window from the left by subtracting the leftmost element from current_sum and incrementing left.
Count Subarrays: For every position of the right pointer, increment the count by the length of the current window, as all these subarrays have scores less than k.
Return Result: Return the final count.

This approach ensures that we consider all valid subarrays and efficiently counts them without explicitly generating each subarray.

Identifying Problem Isomorphism

“Count Subarrays With Score Less Than K” can be mapped to “Subarray Product Less Than K”.

Both involve finding subarrays in a given array based on a certain criteria. In “Count Subarrays With Score Less Than K”, the objective is to count subarrays where the “score” is less than K (where the exact definition of “score” depends on the specifics of the problem). In “Subarray Product Less Than K”, the objective is to count subarrays where the product of all elements is less than K.

The mapping arises from the structure of the problem: traversing the array to find valid subarrays according to a certain condition, and then counting those subarrays. While the exact condition differs between the two problems, the structure and methodology of finding and counting the valid subarrays is analogous.

“Subarray Product Less Than K” is simpler if “score” in the first problem involves complex calculations or operations, as the “Subarray Product Less Than K” problem involves only multiplication of the elements.

“2302. Count Subarrays With Score Less Than K” involves prefix sums, binary search, and managing subarrays. Here are 10 problems to build a foundation for these concepts:

325. Maximum Size Subarray Sum Equals k: This problem involves finding subarrays with a given sum, which is helpful in understanding how to manage subarrays.
560. Subarray Sum Equals K: This is another problem which involves finding subarrays with a given sum.
1074. Number of Submatrices That Sum to Target: This problem involves prefix sums and counting subarrays, similar to the target problem but in two dimensions.
974. Subarray Sums Divisible by K: This problem involves the concept of modular arithmetic and subarray sums, building a foundation for similar concepts in the target problem.
53. Maximum Subarray: This problem helps you understand how to deal with subarrays.
209. Minimum Size Subarray Sum: This problem involves finding a subarray with a sum greater than or equal to a target value.
704. Binary Search: This problem gives a basic understanding of binary search.
33. Search in Rotated Sorted Array: This problem provides an interesting twist on binary search.
34. Find First and Last Position of Element in Sorted Array: This problem uses binary search to find the first and last occurrence of a target value.
287. Find the Duplicate Number: This problem involves using binary search in a slightly non-traditional way.

These cover subarray handling, prefix sums, and binary search, which are key to solving the problem “2302. Count Subarrays With Score Less Than K”.

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: