Count Subarrays With Score Less Than K - Solution & Explanation
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.
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
Approach Overview
Problem 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 1: Sliding Window Method
The 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.
Complexity
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.
Approach 2: Prefix Sum and Binary Search
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.
Complexity
Time Complexity: O(n^2), as each subarray is evaluated.
Space Complexity: O(n), due to the prefix sums storage.
Approach 3: Prefix Sum + Binary Search
First, we calculate the prefix sum array s of the array nums, where s[i] represents the sum of the first i elements of nums.
Next, we enumerate each element of nums as the last element of a subarray. For each element, we can use binary search to find the maximum length l such that s[i] - s[i - l] times l < k. The number of subarrays ending at this element is l, and summing up all l gives the final answer.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
Approach 4: Two Pointers
We can use the two-pointer technique to maintain a sliding window such that the sum of elements in the window is less than k. The number of subarrays ending at the current element is equal to the length of the window. Summing up all the window lengths gives the final answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| 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. |
| Prefix Sum + Binary Search | — |
| Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count Subarrays With Score Less Than K | Leetcode 2302 • Techdose • 3,836 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Subarrays With Score Less Than K easy or hard?
Count Subarrays With Score Less Than K Python/Java solution
How to solve Count Subarrays With Score Less Than K in O(n)?
What is the best approach for Count Subarrays With Score Less Than K?
Is Count Subarrays With Score Less Than K asked at Google/Amazon/Meta?
What data structure is used in Count Subarrays With Score Less Than K?
What is the time complexity of Count Subarrays With Score Less Than K?
Ready to solve this problem?
Practice Count Subarrays With Score Less Than K with our built-in code editor and test cases.
Practice on FleetCode