Count Subarrays With Score Less Than K

Hard

8 views

Topics:

ArraysSliding Windows

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: 5
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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10¹⁵

Count Subarrays With Score Less Than K

Hard

8 views

Topics:

ArraysSliding Windows

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: 5
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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10¹⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`? Specifically, what is the maximum possible size of `nums` and the maximum possible value of `k`?
Can the elements in the `nums` array be negative, zero, or only positive integers?
If there are no subarrays with a score less than `k`, what value should I return?
Are we looking for contiguous subarrays only, or can the subarrays be non-contiguous?
Could `k` be zero or negative?

Brute Force Solution

Approach

The brute force approach to counting qualifying subarrays involves examining every possible subarray to see if it meets the condition. We will methodically generate and evaluate each subarray individually. If it does, we count it and continue until all subarrays are checked.

Here's how the algorithm would work step-by-step:

Consider the initial part of the list, consisting of only the first element.
Check if this small part fulfills the requirement.
Now, look at the first two elements as a group. Does this group fulfill the requirement?
Continue expanding the group from the beginning, adding one more element each time, and checking if the requirement is met. Stop once the group includes all elements from the original list.
Next, shift the focus to start from the second element in the original list. Again, consider the smallest group (just the second element), then expand it by adding the next element, and so on, checking the requirement each time.
Repeat this shifting and expanding process, moving through the original list one element at a time, until you have considered all possible groups that start from each position.
Each time a group fulfills the requirement, increment a special counter.
After examining all possible groups, the final count in the special counter is the answer.

Code Implementation

def count_subarrays_brute_force(numbers, target_score):
    subarray_count = 0

    # Iterate through all possible starting indices
    for start_index in range(len(numbers)):
        
        # Iterate through all possible ending indices for each starting index
        for end_index in range(start_index, len(numbers)):
            current_subarray = numbers[start_index : end_index + 1]
            subarray_sum = 0
            
            # Calculate sum of current subarray
            for number in current_subarray:
                subarray_sum += number
                
            subarray_score = subarray_sum * len(current_subarray)
            
            # Check if the score of the subarray is less than the target
            if subarray_score < target_score:
                # Increment the count because it meets the requirement.
                subarray_count += 1

    return subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. For each starting index i, it considers all subarrays starting at i, which involves iterating up to n-i elements. This results in nested loops, where the outer loop iterates from 0 to n-1, and the inner loop iterates from i to n-1. The total number of operations is proportional to 1 + 2 + ... + n, which is approximately n * (n+1) / 2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach iterates through subarrays, but the plain English description does not mention any auxiliary data structures to store intermediate results like subarrays or visited indices. Only a counter to track qualifying subarrays is used, which takes constant space. The space used by index variables and the counter does not scale with the input size N, where N is the length of the input array. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to count the number of groups of consecutive numbers where the product of their sum and length is less than a target value. Instead of checking every possible group, we use a clever method where we grow and shrink the group based on whether its score is too high or just right.

Here's how the algorithm would work step-by-step:

Start with an empty group at the beginning of the numbers.
Keep adding numbers to the right end of the group until the 'score' (sum times length) of the group becomes too big.
If the score is too big, start removing numbers from the left end of the group until the score is small enough again.
Each time you have a valid group (score less than the target), count how many numbers are in the group, because that is how many valid subarrays end at the current 'right' position.
Move to the next number on the right and repeat the process of adding and removing numbers to keep the score below the target.
Continue until you have checked all the numbers. The final count is the total number of valid groups.
By growing and shrinking the group like this, we efficiently explore all possible groups without checking unnecessary ones.

Code Implementation

def count_subarrays_with_score_less_than_k(numbers, target_score):
    number_of_subarrays = 0
    current_subarray_sum = 0
    left_index = 0

    for right_index in range(len(numbers)):
        current_subarray_sum += numbers[right_index]

        # Shrink the subarray from the left if the score is too high.
        while (current_subarray_sum * (right_index - left_index + 1)) >= target_score and left_index <= right_index:

            current_subarray_sum -= numbers[left_index]
            left_index += 1

        #If left index exceeds right, no valid subarrays end at right index.
        if left_index > right_index:
            continue

        # Each valid subarray ending at right_index is counted
        number_of_subarrays += (right_index - left_index + 1)

    return number_of_subarrays

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n using a sliding window approach. The outer loop progresses through each element of the array once. The inner while loop adjusts the window's starting position. Crucially, each element is added to and removed from the window at most once. Therefore, both the outer and inner loops effectively iterate at most n times in total, leading to a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm maintains a sliding window defined by two pointers (left and right). It also uses a variable to store the current sum of the subarray within the window, and another to keep track of the count. These variables take up constant space, irrespective of the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 immediately because there are no subarrays.
k is zero or negative.	Return 0 because no subarray can have a strictly negative score.
nums contains negative numbers	The sum of a subarray can be negative; consider how this affects the score (length * sum) compared to k.
nums contains zero	Zeroes can reduce the sum of subarrays, potentially causing a valid score where it might not have existed otherwise.
nums contains large positive numbers that could cause integer overflow when summing or when calculating the score (length * sum)	Use long data type to store the sum and score to prevent integer overflow.
k is a very large number	Ensure the algorithm is efficient enough to avoid unnecessary computations when all subarrays might have a score less than k.
All elements in nums are the same.	The sum and the score will increase linearly with the length; consider how to efficiently calculate the number of valid subarrays.
Maximum sized input array (nums is very large)	The algorithm should use O(n) space complexity (sliding window) to avoid exceeding memory limits.