We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Subarrays With Score Less Than K

Number: 2394

Difficulty: Hard

Paid? No

Companies: Pinterest, Google

Problem Description

Given an array of positive integers and an integer k, count the number of non-empty contiguous subarrays (subarrays) whose "score" is strictly less than k. The score of a subarray is defined as (subarray sum) multiplied by (length of the subarray).

Key Insights

  • The score of a subarray ending at index r starting from index l is: (sum of subarray) * (number of elements).
  • Since all numbers are positive, extending a window (adding elements) will increase both the sum and its length, thus increasing the score.
  • If a window [l, r] is valid (i.e. score < k), then any subarray ending at r and starting from an index i where l ≤ i ≤ r is also valid, because removing prefix elements decreases both the sum and the length.
  • A two-pointer (sliding window) approach can be applied incrementally: expand the window on the right and if the condition fails, move the left pointer until the score is less than k again.
  • The computed count for each valid window ending at r is (r - l + 1).

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array, since each element is processed at most twice. Space Complexity: O(1), aside from the input array.

Solution

We maintain two pointers, left and right, and a running sum for the current window. For each right pointer from 0 to n - 1, we add the new element to the running sum. Then, while the current window’s score, calculated as (window sum) * (window length), is greater than or equal to k, we shrink the window from the left. Once the window becomes valid, we add the number of valid subarrays ending at right, which is the current window size, to the answer. This works because any subarray ending at right within the current window is guaranteed to have a lower score due to the reduction in both sum and length once we drop elements from the start.

Code Solutions

# Python solution with inline comments
class Solution:
    def countSubarrays(self, nums, k):
        count = 0           # To store the total count of valid subarrays
        window_sum = 0      # Running sum of the current window
        left = 0            # Left pointer of the window

        # Iterate with right pointer over the array
        for right in range(len(nums)):
            window_sum += nums[right]  # Include new element in the window

            # Shrink the window from the left until the score is strictly less than k
            # Score = window_sum * (window length)
            while left <= right and window_sum * (right - left + 1) >= k:
                window_sum -= nums[left]  # Remove element at the left from current sum
                left += 1                 # Move left pointer forward

            # All subarrays ending at right starting from index [left, right] are valid
            count += (right - left + 1)
        
        return count

# Example usage:
# sol = Solution()
# print(sol.countSubarrays([2,1,4,3,5], 10))  # Output should be 6
← Back to All Questions