LeetCode Entry

2302. Count Subarrays With Score Less Than K

28.04.2025 hard 2025 kotlin rust

Subarrays sum cnt <= k pointers

2302. Count Subarrays With Score Less Than K hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/972

Problem TLDR

Subarrays sum * cnt <= k #hard #two_pointers

Intuition

This is a standart two-pointers pattern task: always move the right pointer, move the left util condition, count how many good subarray starting point are.

Approach

• you can use i - j + 1 or a separate count variable
• careful with int overflow

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

// 28ms
    fun countSubarrays(n: IntArray, k: Long): Long {
        var s = 0L; var j = 0
        return n.withIndex().sumOf { (i, x) ->
            s += x; while (s * (i - j + 1) >= k) s -= n[j++]
            1L + i - j
        }
    }

// 3ms
    fun countSubarrays(n: IntArray, k: Long): Long {
        var s = 0L; var r = 0L; var j = 0
        for ((i, x) in n.withIndex()) {
            s += x
            while (s * (i - j + 1) >= k) s -= n[j++]
            r += i - j + 1
        }
        return r
    }

// 0ms
    pub fn count_subarrays(n: Vec<i32>, k: i64) -> i64 {
        let (mut s, mut j) = (0, 0);
        n.iter().enumerate().map(|(i, &x)| {
            s += x as i64;
            while s * (i - j + 1) as i64 >= k { s -= n[j] as i64; j += 1 }
            i - j + 1
        }).sum::<usize>() as _
    }

// 0ms
    long long countSubarrays(vector<int>& n, long long k) {
        long long s = 0, r = 0; int j = 0, c = 0;
        for (int x: n) {
            s += x; ++c;
            while (c * s >= k) s -= n[j++], --c;
            r += c;
        } return r;
    }