Intuition¶

The problem asks us to determine the number of non-empty subarrays of nums whose score is strictly less than k.

Key Insight:

Subarrays are contiguous.
Positive integers means:
sum increases as we add more elements.
product increases as we add more elements.
We want an efficient method, not O(n²) brute-force.

Approach (Sliding window)¶

Maintain a window [left..right].
Keep track of sum inside the window.
Expand right to include more elements.
If (sum * length) >= k, then move left to shrink the window until it’s valid.
For each right, number of valid subarrays ending at right is (right - left + 1).

Complexity¶

Time Complexity:

O(N) where N is the number of elements in array.

Space Complexity:

O(1) for extra space.

Code¶

Go¶

func countSubarrays(nums []int, k int64) int64 {
    count, sum := 0, 0
    for left, right := 0, 0; right < len(nums); right++ {
        sum += nums[right]
        for sum * (right-left+1) >= int(k) {
            sum -= nums[left]
            left++
        }
        count += right - left + 1
    }
    return int64(count)
}

Rust¶

impl Solution {
    pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
        let (mut ans, mut sum, mut left) = (0, 0, 0);
        for right in 0..nums.len() {
            sum += nums[right] as i64;
            while sum * (right - left + 1) as i64 >= k {
                sum -= nums[left] as i64;
                left += 1;
            }
            ans += right - left + 1;
        }
        ans as i64
    }
}