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 <= 1015In #2302 Count Subarrays With Score Less Than K, the score of a subarray is defined as the product of its sum and length. The goal is to count how many subarrays have a score strictly less than k. A key observation is that when all numbers are positive, expanding the subarray increases both the sum and the score. This property allows an efficient sliding window strategy.
Maintain a running prefix sum (or window sum) while expanding the right pointer. If the current score (sum * window_length) becomes greater than or equal to k, shrink the window from the left until the condition is satisfied again. For every valid window ending at the current index, you can count all subarrays that end there.
This technique avoids checking every subarray explicitly and reduces the complexity significantly. Alternative reasoning may involve prefix sums with binary search, but the sliding window approach typically yields the most efficient implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Running Sum | O(n) | O(1) |
| Prefix Sum + Binary Search | O(n log n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
If we add an element to a list of elements, how will the score change?
How can we use this to determine the number of subarrays with score less than k in a given range?
How can we use “Two Pointers” to generalize the solution, and thus count all possible subarrays?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sliding window works because the array elements are positive, meaning the subarray sum grows as the window expands. If the score becomes too large, moving the left pointer reduces the sum and window size, restoring the condition. This monotonic behavior enables linear traversal.
Yes, variations of this problem appear in coding interviews at top tech companies. It tests understanding of sliding window patterns, prefix sums, and how to optimize brute-force subarray enumeration into linear-time solutions.
The optimal approach uses a sliding window with a running sum. Since all array values are positive, expanding the window increases the score, allowing us to shrink the window when the score exceeds k. This results in an efficient O(n) solution.
The problem mainly relies on arrays and a running prefix or window sum. No complex data structures are required, but maintaining a cumulative sum helps compute subarray scores efficiently during the sliding window process.