How hard is LeetCode 2302. Count Subarrays With Score Less Than K?

LeetCode 2302. Count Subarrays With Score Less Than K is rated Hard on LeetCode.

What is the time complexity of LeetCode 2302. Count Subarrays With Score Less Than K?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2302. Count Subarrays With Score Less Than K?

The Python solution on this page uses O(n), where n is the length of the array \textit{nums} auxiliary space.

What topics does LeetCode 2302. Count Subarrays With Score Less Than K cover?

LeetCode 2302. Count Subarrays With Score Less Than K is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.

Count Subarrays With Score Less Than K — LeetCode 2302 Python Solution

HardArrayBinary SearchPrefix SumSliding Window

Problem: #2302
Pattern: Sliding Window
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: nums = [2,1,4,3,5], k = 10
Output: 6
Explanation: The 6 subarrays having scores less than 10 are:

Python solution

Python

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))
        ans = 0
        for i in range(1, len(s)):
            l, r = 0, i
            while l < r:
                mid = (l + r + 1) >> 1
                if (s[i] - s[i - mid]) * mid < k:
                    l = mid
                else:
                    r = mid - 1
            ans += l
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n), where n is the length of the array \textit{nums} auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2302. Count Subarrays With Score Less Than K is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2302. Count Subarrays With Score Less Than K?: LeetCode 2302. Count Subarrays With Score Less Than K is rated Hard on LeetCode.
What is the time complexity of LeetCode 2302. Count Subarrays With Score Less Than K?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2302. Count Subarrays With Score Less Than K?: The Python solution on this page uses O(n), where n is the length of the array \textit{nums} auxiliary space.
What topics does LeetCode 2302. Count Subarrays With Score Less Than K cover?: LeetCode 2302. Count Subarrays With Score Less Than K is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.