Watch 10 video solutions for Count Subarrays With Score Less Than K, a hard level problem involving Array, Binary Search, Sliding Window. This walkthrough by codestorywithMIK has 8,819 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1015Problem Overview: Given an array nums and an integer k, count the number of contiguous subarrays where score = sum(subarray) * length(subarray) is strictly less than k. The challenge is evaluating many subarrays efficiently without recomputing sums repeatedly.
Approach 1: Sliding Window Method (O(n) time, O(1) space)
This is the optimal solution. Maintain a window with two pointers left and right while tracking the running sum of the current window. As you extend the window by moving right, update the sum and check whether sum * window_length is still less than k. If the score becomes too large, move left forward and subtract values from the sum until the constraint holds again. For every valid right, all subarrays ending at that index and starting between left and right are valid, so add right - left + 1 to the answer. Each element enters and leaves the window at most once, giving linear time complexity. This technique is a classic application of the sliding window pattern on positive arrays.
Approach 2: Prefix Sum and Binary Search (O(n log n) time, O(n) space)
Precompute a prefix array where prefix[i] stores the sum of the first i elements. For each starting index i, you want the largest ending index j such that (prefix[j] - prefix[i]) * (j - i) < k. Because the prefix sum is monotonic when numbers are positive, you can binary search the maximum valid j. This approach separates sum computation using prefix sums and boundary search using binary search. It is slightly slower than sliding window but still efficient and easier to reason about if you prefer explicit range queries.
Recommended for interviews: The sliding window approach is the expected solution. It demonstrates recognition of monotonic constraints and efficient two‑pointer window expansion. The prefix sum + binary search variant shows deeper algorithmic thinking but is rarely required once you realize the window can shrink dynamically.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution when array values are positive and window can shrink dynamically |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Useful when you want explicit range sums and search for the maximum valid end index |