Count Subarrays With Score Less Than K

Hard
1354.

Count Subarrays With Score Less Than K

Count Subarrays With Score Less Than K is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon and Google interviews.

The score of an array is the sum of its elements multiplied by its length. For example, the score of [1,2,3,4,5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given an array nums of positive integers and an integer k, return the number of non-empty contiguous subarrays of nums whose score is strictly less than k.

CodeKairo note: the original problem allows k up to 10^15 and returns a 64-bit count; here nums.length and k are bounded so the answer fits in a 32-bit integer. Intermediate scores can still exceed 32 bits — compute them in 64-bit.

Example 1

Input
nums = [3,1,5,2], k = 12
Output
5
Explanation
The four single elements plus `[3,1]` (score 8). `[1,5]` scores exactly 12, which is not less than 12.

Example 2

Input
nums = [1,2,1,2], k = 7
Output
7
Explanation
Four singles and the three pairs (each score 6); every triple scores at least 12.

Example 3

Input
nums = [10], k = 10
Output
0

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Subarrays With Score Less Than K — Problem & Solution

Count Subarrays With Score Less Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count Subarrays With Score Less Than K is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon and Google interviews.

Problem statement

The score of an array is the sum of its elements multiplied by its length. For example, the score of [1,2,3,4,5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given an array nums of positive integers and an integer k, return the number of non-empty contiguous subarrays of nums whose score is strictly less than k.

CodeKairo note: the original problem allows k up to 10^15 and returns a 64-bit count; here nums.length and k are bounded so the answer fits in a 32-bit integer. Intermediate scores can still exceed 32 bits — compute them in 64-bit.

Example 1

Input: nums = [3,1,5,2], k = 12
Output: 5
Explanation: The four single elements plus `[3,1]` (score 8). `[1,5]` scores exactly 12, which is not less than 12.

Example 2

Input: nums = [1,2,1,2], k = 7
Output: 7
Explanation: Four singles and the three pairs (each score 6); every triple scores at least 12.

Example 3

Input: nums = [10], k = 10
Output: 0

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

Hints for Count Subarrays With Score Less Than K

  1. Hint 1

    All values are positive, so extending a subarray only increases its score, and shrinking it only decreases it.

  2. Hint 2

    For each right end, the valid left ends form a suffix ending at that right end. Find the smallest valid left end.

  3. Hint 3

    Slide a window: add nums[right], then drop elements from the left while sum * length >= k. Every window ending at right that starts at or after left is valid, so add right - left + 1.

How to solve Count Subarrays With Score Less Than K

Because every element is positive, the score is monotone under extension: a valid subarray stays valid when you shrink it. So for each right end there is a smallest valid left end, and it never moves backwards — a classic sliding window.

Approach

  1. Keep left = 0, a running sum and an answer ans = 0.
  2. For each right, add nums[right] to sum.
  3. While sum * (right - left + 1) >= k, subtract nums[left] and advance left.
  4. Now every subarray [l, right] with left <= l <= right has score below k; add right - left + 1 to ans.

Why it works

If [left, right] has score below k, then any [l, right] with l > left has a smaller sum and a smaller length, so a smaller score. If [left, right] is too big, then [left, right + 1] is too big as well, so left never needs to move back. Each element enters and leaves the window once, and for every right end we count exactly the valid left ends.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • sum * length can reach about 5·10^13 — use 64-bit arithmetic.
  • The comparison is strict: a score equal to k does not count.
  • When the window empties (left > right), the score is 0, which is below k because k >= 1, so the shrinking loop always stops.

Reference solution

Python

from typing import List

def countSubarrays(nums: List[int], k: int) -> int:
    total = 0
    left = 0
    ans = 0
    for right, v in enumerate(nums):
        total += v
        while total * (right - left + 1) >= k:
            total -= nums[left]
            left += 1
        ans += right - left + 1
    return ans

Java

public static int countSubarrays(int[] nums, int k) {
    long sum = 0, ans = 0;
    int left = 0;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum * (right - left + 1) >= k) {
            sum -= nums[left];
            left++;
        }
        ans += right - left + 1;
    }
    return (int) ans;
}

C++

int countSubarrays(vector<int>& nums, int k) {
    long long sum = 0, ans = 0;
    int left = 0;
    for (int right = 0; right < (int) nums.size(); right++) {
        sum += nums[right];
        while (sum * (right - left + 1) >= k) {
            sum -= nums[left];
            left++;
        }
        ans += right - left + 1;
    }
    return (int) ans;
}

JavaScript

var countSubarrays = function(nums, k) {
    var sum = 0, left = 0, ans = 0;
    for (var right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum * (right - left + 1) >= k) {
            sum -= nums[left];
            left++;
        }
        ans += right - left + 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search