Sliding Window : 3

Day 2/75:

Question: Count Subarrays With Score Less Than K- (Hard)

Problem Statement: 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.

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.        

Approach:

• Initialization:We initialize two pointers, start and end, to mark the boundaries of our window.Initialize the sum variable to 0, the sum of elements of current window.Initialize the count variable to 0, which will keep track of the number of valid subarrays.
• Sliding Window Technique:
• Start with two pointers, one at the beginning and one at the end of the array.
• Move the end pointer forward, adding each element to the sum.
• If the sum of the current window multiplied by its size is greater than or equal to K, shrink the window from the left until it's within the target range.
• Count the number of subarrays formed by the valid windows.
• Repeat this process until you reach the end of the array.Result: Return the total count of valid subarrays.

Time Complexity: The time complexity of this approach is O(N), where N is the length of the input array. We traverse the array only once with our sliding window, making it a linear time solution.

Space Complexity: The space complexity is O(1) since we use a constant amount of extra space for variables, regardless of the input size. Hence, our solution is memory-efficient.