DDSA Solutions

2302. Count Subarrays With Score Less Than K

HardView on LeetCode
ArrayBinary SearchPrefix SumSliding Window
Time: O(n)
Space: O(1)

Problem Overview

Count subarrays with score < k, where score = sum * length.

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems