Count Subarrays With Score Less Than K

Problem Description

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. The score of an array is defined as the product of its sum and its length.

Key Insights

• The score of a subarray is calculated as (sum of elements) * (number of elements).
• We need to find all contiguous subarrays with a score less than k.
• A sliding window technique can be utilized to efficiently calculate the sum and length of subarrays.
• The constraints allow for an O(n) solution, making a brute-force approach inefficient.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a sliding window approach. We maintain a window that expands to include new elements and contracts when the score exceeds k. By keeping track of the sum and the number of elements in the current window, we can calculate the score and determine how many valid subarrays exist.

1. Initialize variables to keep track of the sum and the number of valid subarrays.
2. Use two pointers (start and end) to represent the current window.
3. Expand the end pointer to include new elements and update the sum.
4. If the score (sum * length) is not less than k, move the start pointer to reduce the window size until the score is valid again.
5. Count the number of valid subarrays formed by the current end pointer position.

Code Solutions