2302. Count Subarrays With Score Less Than K

HardView on LeetCode

Array Binary Search Prefix Sum Sliding Window

Time: O(n)

Space: O(1)

Intuition

Count subarrays with score < k, where score = sum * length. Sliding window: expand right, shrink left when score >= k.

Algorithm

1Window [l,r]. Maintain sum. While sum * (r-l+1) >= k: l++. Add r-l+1 subarrays ending at r.

Common Pitfalls

•Score is sum*length. Window shrinks from left when score exceeds k.

2302.cs

// Approach: Sliding window; shrink left when sum * length >= k; count valid right positions.
// Time: O(n) Space: O(1)

public class Solution
{
    public long CountSubarrays(int[] nums, long k)
    {
        long ans = 0;
        long sum = 0;

        for (int l = 0, r = 0; r < nums.Length; ++r)
        {
            sum += nums[r];
            while (sum * (r - l + 1) >= k)
                sum -= nums[l++];
            ans += r - l + 1;
        }

        return ans;
    }
}

Was this solution helpful?