2302. Count Subarrays With Score Less Than K

[mah-shamim]

Topics: Array, Binary Search, Sliding Window, Prefix Sum

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.

Example 1:

• Input: nums = [2,1,4,3,5], k = 10
• Output: 6
• Explanation: The 6 subarrays having scores less than 10 are:
  • [2] with score 2 * 1 = 2.
  • [1] with score 1 * 1 = 1.
  • [4] with score 4 * 1 = 4.
  • [3] with score 3 * 1 = 3.
  • [5] with score 5 * 1 = 5.
  • [2,1] with score (2 + 1) * 2 = 6.
    Note that subarrays such as [1,4] and [4,3,5] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10.

Example 2:

• Input: nums = [1,1,1], k = 5
• Output: 4
• Explanation:
  Every subarray except [1,1,1] has a score less than 5.
  [1,1,1] has a score (1 + 1 + 1) * 3 = 9, which is greater than 5.
  Thus, there are 5 subarrays having scores less than 5.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= 1015

Hint:

1. If we add an element to a list of elements, how will the score change?
2. How can we use this to determine the number of subarrays with score less than k in a given range?
3. How can we use “Two Pointers” to generalize the solution, and thus count all possible subarrays?

[mah-shamim]

We need to count the number of non-empty subarrays of a given array whose score (defined as the product of the subarray's sum and its length) is strictly less than a given integer k. Given the constraints, an efficient approach is necessary to avoid a brute-force solution.

Approach

The key insight here is that for a given starting index i, the score of the subarray starting at i and ending at j increases as j increases. This allows us to use a binary search approach to efficiently determine the maximum valid j for each starting index i.

1. Prefix Sum Array: Compute a prefix sum array to quickly calculate the sum of any subarray.
2. Binary Search: For each starting index i, use binary search to find the maximum ending index j such that the score of the subarray from i to j is less than k.
3. Count Valid Subarrays: For each valid starting index i, the number of valid subarrays ending at j is j - i + 1.

Let's implement this solution in PHP: 2302. Count Subarrays With Score Less Than K

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function countSubarrays($nums, $k) {
    $n = count($nums);
    $prefix = array_fill(0, $n + 1, 0);
    for ($i = 0; $i < $n; $i++) {
        $prefix[$i + 1] = $prefix[$i] + $nums[$i];
    }
    $count = 0;
    for ($i = 0; $i < $n; $i++) {
        $low = $i;
        $high = $n - 1;
        $best_j = -1;
        while ($low <= $high) {
            $mid = (int)(($low + $high) / 2);
            $sum = $prefix[$mid + 1] - $prefix[$i];
            $length = $mid - $i + 1;
            $product = $sum * $length;
            if ($product < $k) {
                $best_j = $mid;
                $low = $mid + 1;
            } else {
                $high = $mid - 1;
            }
        }
        if ($best_j != -1) {
            $count += ($best_j - $i + 1);
        }
    }
    return $count;
}

// Example 1
$nums = [2, 1, 4, 3, 5];
$k = 10;
echo countSubarrays($nums, $k) . "\n"; // Output: 6

// Example 2
$nums = [1, 1, 1];
$k = 5;
echo countSubarrays($nums, $k) . "\n"; // Output: 5
?>

Explanation:

1. Prefix Sum Array: The prefix sum array allows us to compute the sum of any subarray in constant time. For example, the sum of the subarray from index i to j can be found using prefix[j+1] - prefix[i].

2. Binary Search: For each starting index i, we perform a binary search on the possible ending indices j. The binary search helps efficiently determine the largest j such that the score of the subarray [i, j] is less than k.

3. Counting Valid Subarrays: Once the maximum valid j is found for a starting index i, all subarrays starting at i and ending at any index from i to j are valid. The count of such subarrays is j - i + 1.

This approach ensures that we efficiently count all valid subarrays in O(n log n) time, making it suitable for large input sizes up to 10⁵.

[kovatz]

Thanks for solving the problem of "Count Subarrays With Score Less Than K"

[mah-shamim]

Thanks