LeetCode 2302: Count Subarrays With Score Less Than K

The problem "Count Subarrays With Score Less Than K" (LeetCode 2302) requires us to count the number of non-empty subarrays where the product of the subarray's sum and its length is strictly less than a given integer k. This problem tests our ability to optimize subarray calculations and is a classic example of when the sliding window technique shines.

Problem Statement

The score of an array is defined as the product of its sum and its length.

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.

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 105
• 1 ≤ k ≤ 1015

Problem Link

View on LeetCode ↗

Example 1

Input: nums = [2,1,4,3,5], k = 10
Output: 6
Explanation:
The 6 subarrays having scores less than 10 are:
- [2] → score = 2 × 1 = 2
- [1] → 1 × 1 = 1
- [4] → 4 × 1 = 4
- [3] → 3 × 1 = 3
- [5] → 5 × 1 = 5
- [2,1] → (2+1) × 2 = 6
Note that subarrays like [1,4] and [4,3,5] have scores of 10 and 36 respectively,
which are not 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 = 1
- [1] → 1 × 1 = 1
- [1] → 1 × 1 = 1
- [1,1] → (1+1) × 2 = 4
- [1,1] → (1+1) × 2 = 4
The subarray [1,1,1] has score (1+1+1) × 3 = 9, which is not less than 5.

Approach 1: Brute Force (TLE)

The brute force approach checks every possible subarray and calculates its score. While straightforward, this approach results in O(n²) time complexity, which is too slow for the upper constraint of n ≤ 10⁵.

Algorithm Steps

1. Initialize a counter to zero
2. Iterate through all possible starting indices
3. For each starting index, expand the subarray to the right
4. Calculate the score for each subarray
5. Increment counter if score < k
6. Break early if score ≥ k (since longer subarrays will have higher scores)
7. Return the final count

Complexity Analysis

Why it fails: For n = 10⁵, the number of operations would be around 10¹⁰, which is way beyond what's acceptable (typically need to stay under 10⁶ operations).

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        int n = nums.size();
        long long count = 0;
        
        for(int i = 0; i < n; i++) {
            long long sum = 0;
            for(int j = i; j < n; j++) {
                sum += nums[j];
                long long score = sum * (j - i + 1);
                
                if(score < k) {
                    count++;
                } else {
                    break; // Longer subarrays will have higher scores
                }
            }
        }
        
        return count;
    }
};
                

class Solution {
    public long countSubarrays(int[] nums, long k) {
        int n = nums.length;
        long count = 0;
        
        for(int i = 0; i < n; i++) {
            long sum = 0;
            for(int j = i; j < n; j++) {
                sum += nums[j];
                long score = sum * (j - i + 1);
                
                if(score < k) {
                    count++;
                } else {
                    break; // Longer subarrays will have higher scores
                }
            }
        }
        
        return count;
    }
}
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                score = current_sum * (j - i + 1)
                
                if score < k:
                    count += 1
                else:
                    break  # Longer subarrays will have higher scores
                    
        return count
                

Approach 2: Sliding Window (Optimal)

The optimal solution uses a sliding window technique to maintain a window where the score is less than k. This approach works because with positive numbers, expanding the window increases the score, and shrinking it decreases the score.

Key Insights

• All elements are positive, so expanding window increases score
• For each right pointer, find the smallest left where window is valid
• Number of valid subarrays ending at right is window length

Algorithm Steps

1. Initialize left pointer, sum, and count to 0
2. Iterate with right pointer from 0 to n-1
3. Add nums[right] to the current sum
4. While score (sum × window length) ≥ k:
   • Subtract nums[left] from sum
   • Move left pointer forward
5. Add window length to count (all subarrays ending at right)
6. Return the total count

Complexity Analysis

Explanation: Each element is processed exactly twice (added once when window expands and removed once when window contracts), resulting in O(n) time complexity.

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long count = 0;
        long long sum = 0;
        int left = 0;
        int n = nums.size();
        
        for(int right = 0; right < n; right++) {
            sum += nums[right];
            
            // Shrink the window from left while condition is invalid
            while(sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            
            // All subarrays ending at 'right' with start >= left are valid
            count += (right - left + 1);
        }
        
        return count;
    }
};
                

class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0;
        long sum = 0;
        int left = 0;
        int n = nums.length;
        
        for(int right = 0; right < n; right++) {
            sum += nums[right];
            
            // Shrink the window from left while condition is invalid
            while(sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            
            // All subarrays ending at 'right' with start >= left are valid
            count += (right - left + 1);
        }
        
        return count;
    }
}
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        count = 0
        current_sum = 0
        left = 0
        
        for right in range(len(nums)):
            current_sum += nums[right]
            
            # Shrink the window from left while condition is invalid
            while current_sum * (right - left + 1) >= k:
                current_sum -= nums[left]
                left += 1
                
            # All subarrays ending at 'right' with start >= left are valid
            count += (right - left + 1)
            
        return count
                

Edge Cases and Special Considerations

When implementing solutions for this problem, consider these edge cases:

1. Single Element Arrays

Input: nums = [5], k = 10
Output: 1 (5 × 1 = 5 < 10)

Input: nums = [10], k = 5
Output: 0 (10 × 1 = 10 ≥ 5)

2. All Elements Equal

Input: nums = [2,2,2,2], k = 10
Output: 4
[2]×1=2, [2]×1=2, [2]×1=2, [2]×1=2
No subarrays of length ≥2 have score < 10:
[2,2]×2=8, [2,2,2]×3=18, etc.

3. Large k Values

Input: nums = [1,2,3,...,100000], k = 1015
Output: n*(n+1)/2 ≈ 5×109 (all possible subarrays)
Must handle large counts efficiently

4. Minimum/Maximum Values

Input: nums = [1,1,1,...,1] (105 elements), k = 2
Output: 105 (only single-element subarrays qualify)

Comparison of Approaches

Frequently Asked Questions