Problem Informations

• Problem Index: 2302
• Problem Link: Count Subarrays With Score Less Than K
• Topics: Array, Binary Search, Sliding Window, Prefix Sum

Problem Description

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) \times 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 \times 1 = 2$.
  • [1] with score $1 \times 1 = 1$.
  • [4] with score $4 \times 1 = 4$.
  • [3] with score $3 \times 1 = 3$.
  • [5] with score $5 \times 1 = 5$.
  • [2,1] with score $(2 + 1) \times 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) \times 3 = 9$, which is greater than 5.
  Thus, there are 5 subarrays having scores less than 5.

Constraints:

• $1 \leq \text{nums.length} \leq 10^5$
• $1 \leq \text{nums}[i] \leq 10^5$
• $1 \leq k \leq 10^{15}$

Intuition

The problem involves finding the number of subarrays within a given array of positive integers where the score, defined as the product of the subarray’s sum and its length, is strictly less than a given integer $k$. Since the constraints allow the array length and elements to be quite large (up to $10^5$), an efficient method is required to solve the problem in reasonable time. A brute force solution that generates all possible subarrays and calculates their scores would be computationally prohibitive due to its potentially quadratic time complexity.

To address this, we can use a two-pointer or sliding window technique that dynamically calculates the sum of elements in a subarray while adjusting its boundaries to maintain valid scores. This method is efficient as it avoids redundant calculations by maintaining a running sum and dynamically adjusting the window size.

Approach

The solution employs the sliding window approach, which involves the use of two pointers to delineate the start and end of the current subarray being assessed. The key steps are as follows:

1. Initialize Variables:

   • totalSubarrays to count the valid subarrays.
   • currentSum to store the sum of the current subarray.
   • left as the starting pointer of the current subarray window.

2. Iterate Over the Array:

   • Use a right pointer to iterate over each element of the array, which serves as the end of the current subarray.
   • For each element nums[right], add its value to currentSum.

3. Adjust the Sliding Window:

   • While the score of the current subarray (currentSum * (right - left + 1)) is greater than or equal to $k$, reduce the window size by removing the element at the left index from currentSum, and increment the left pointer. This ensures that the subarray score remains less than $k$.

4. Count Valid Subarrays:

   • After adjusting the window, all subarrays ending at right with starting points from left to right are valid. Thus, increment totalSubarrays by right - left + 1.

5. Return the Result:

   • The totalSubarrays variable accumulates the count of all valid subarrays throughout the iteration, which is returned as the final result.

This approach efficiently evaluates each element at most twice (as the right pointer moves forward and the left pointer may also move forward to adjust the window), resulting in a time complexity of $O(n)$, where $n$ is the length of the array. This ensures the solution’s ability to handle large input sizes within reasonable computational limits.

Code

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long totalSubarrays = 0; // Variable to store the count of subarrays with score less than k
        long long currentSum = 0;     // Stores the current sum of the subarray
        long long arrayLength = nums.size(); // Length of the input array
        long long left = 0;           // Left pointer for the sliding window
        
        // Iterate through the array with the right pointer forming the end of the subarray
        for (long long right = 0; right < arrayLength; right++) {
            currentSum += nums[right]; // Add current element to the subarray sum
            
            // Check if the subarray score is not less than k, adjust left boundary
            while (currentSum * (right - left + 1) >= k) {
                currentSum -= nums[left]; // Remove element at left from the sum
                left++;                   // Move left pointer to narrow the window
            }
            
            // Add the number of valid subarrays ending at `right`
            totalSubarrays += right - left + 1;
        }
        
        return totalSubarrays;
    }
};

Python

class Solution:
    def countSubarrays(self, nums, k):
        totalSubarrays = 0  # Variable to store the count of subarrays with score less than k
        currentSum = 0      # Stores the current sum of the subarray
        arrayLength = len(nums)  # Length of the input array
        left = 0            # Left pointer for the sliding window
        
        # Iterate through the array with the right pointer forming the end of the subarray
        for right in range(arrayLength):
            currentSum += nums[right]  # Add current element to the subarray sum
            
            # Check if the subarray score is not less than k, adjust left boundary
            while currentSum * (right - left + 1) >= k:
                currentSum -= nums[left]  # Remove element at left from the sum
                left += 1                 # Move left pointer to narrow the window
            
            # Add the number of valid subarrays ending at `right`
            totalSubarrays += right - left + 1
        
        return totalSubarrays

Complexity

• Time complexity: $O(n)$
  The algorithm uses a sliding window technique with two pointers, left and right, where right iterates over the entire array exactly once and left moves incrementally. Therefore, the total number of operations within the loop is proportional to the size of the array, leading to a time complexity of $O(n)$, where $n$ is the length of nums.
• Space complexity: $O(1)$
  The space complexity is $O(1)$ because the solution only uses a fixed amount of additional space that does not grow with the input size. Variables such as totalSubarrays, currentSum, and others consume constant space, independent of the input array size.