The score of an array is defined as the product of its sum and its length.
[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:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= 1015The sliding window method allows us to efficiently find subarrays with a score less than k by maintaining a running sum and adjusting the window size dynamically. By expanding and contracting the window, we can iterate through the array in linear time.
This C solution uses a sliding window (or two pointers) approach to find subarrays with a score less than k. It maintains a running sum and extends the window by moving the right pointer. If the score exceeds k, the left pointer is adjusted to reduce the window size. The number of valid subarrays ending at the current right index is counted.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we are using a constant amount of extra space.
This alternative method utilizes prefix sums to preprocess the array, enabling efficient calculation of subarray sums. By combining this with binary search, it's possible to find valid subarrays more explicitly.
This C solution uses prefix sums to precompute cumulative sums of subarrays. The prefix sum allows efficient checking of subarray scores, enabling the counting of subarrays meeting the condition directly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), as each subarray is evaluated.
Space Complexity: O(n), due to the prefix sums storage.
| Approach | Complexity |
|---|---|
| Sliding Window Method | Time Complexity: O(n), where n is the number of elements in the array. |
| Prefix Sum and Binary Search | Time Complexity: O(n^2), as each subarray is evaluated. |
Count Subarray sum Equals K | Brute - Better -Optimal • take U forward • 446,138 views views
Watch 9 more video solutions →Practice Count Subarrays With Score Less Than K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor