2302. Count Subarrays With Score Less Than K

2302. Count Subarrays With Score Less Than K

Difficulty: Hard

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?

Solution:

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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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⁵.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub