Count Subarrays With Score Less Than K
HardPrompt
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:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= 1015
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible non-empty subarray. For each subarray, we calculate its score, which is the product of its sum and length. If the score is less than the given value k, we increment a counter. This method is straightforward but inefficient for large inputs.
Algorithm
- Initialize a counter
countto 0. - Loop through the array with an index
ifrom 0 ton-1to serve as the start of the subarray. - Inside this loop, initialize
currentSum = 0L. - Start a nested loop with an index
jfromiton-1to serve as the end of the subarray. - Add
nums[j]tocurrentSum. - Calculate the subarray's score:
score = currentSum * (j - i + 1). - If
score < k, incrementcount. - If
score >= k, break the inner loop as further extensions of the subarray will also have scores>= k. - After the loops complete, return
count.
Walkthrough
The algorithm uses two nested loops to generate all subarrays. The outer loop fixes the starting index i, and the inner loop iterates through all possible ending indices j from i onwards.
To optimize the calculation of the sum for each subarray nums[i..j], we maintain a running sum. For a fixed i, as j increases, we simply add nums[j] to the sum of the previous subarray nums[i..j-1]. The length of the subarray is j - i + 1.
The score is then (running sum) * (length). If this score is strictly less than k, we increment our total count. A small optimization is added: if a subarray's score meets or exceeds k, we can stop extending it (break the inner loop), because any longer subarray starting at the same index i will have an even larger score, as all numbers are positive.
Due to the potential for large sums and scores (up to 10<sup>15</sup>), it's crucial to use a 64-bit integer type (like long in Java) for the sum, score, and count variables to prevent overflow.
class Solution { public long countSubarrays(int[] nums, long k) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { long currentSum = 0; for (int j = i; j < n; j++) { currentSum += nums[j]; long length = j - i + 1; if (currentSum * length < k) { count++; } else { // Since all numbers are positive, if the score for nums[i..j] // is >= k, the score for any longer subarray starting at i // will also be >= k. We can break the inner loop. break; } } } return count; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. The nested loops lead to a quadratic number of operations in the worst case.
Space
O(1), as we only use a few variables to store the count, sum, and loop indices, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct if implemented properly.
Cons
Highly inefficient with a time complexity of O(n^2).
Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
Solutions
Solution
class Solution { public long countSubarrays ( int [] nums , long k ) { int n = nums . length ; long [] s = new long [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } long ans = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int left = 0 , right = i ; while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if (( s [ i ] - s [ i - mid ]) * mid < k ) { left = mid ; } else { right = mid - 1 ; } } ans += left ; } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.