Count subarrays with score less than k

Array Binary Search Sliding Window Prefix Sum

62.3% acceptance

Feb 25, 2026

1611

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. Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k. A subarray is a contiguous sequence of elements within an array.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

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