Count Subarrays With Score Less Than K

Count Subarrays With Score Less Than K

What is this problem about?

The "Count Subarrays With Score Less Than K interview question" defines the score of a subarray as the product of its sum and its length. You are given an array of positive integers and a target k. You need to count all contiguous subarrays whose score is strictly less than k. For example, the score of [1, 2, 3] is $(1+2+3) imes 3 = 18$.

Why is this asked in interviews?

Companies like Meta and Microsoft ask the "Count Subarrays With Score Less Than K coding problem" to evaluate a candidate's ability to apply the Sliding Window technique to a non-standard condition. Because all elements are positive, the score is "monotonic"—as the subarray grows, the score always increases. This property allows for a highly efficient $O(N)$ solution.

Algorithmic pattern used

This problem is solved using the Sliding Window pattern.

1. Monotonicity: Since all numbers are positive, adding an element increases both the sum and the length, thus increasing the score. This makes the sliding window applicable.
2. Pointers: Use left and right pointers.
3. Expansion: Move right and update the current_sum.
4. Shrink: While (current_sum * (right - left + 1)) >= k:
   • Subtract arr[left] from current_sum and increment left.
5. Counting: For a valid window ending at right, the number of valid subarrays ending there is right - left + 1. Add this to the total count.

Example explanation

Array: [2, 1, 4, 3, 5], $k = 10$

• right=0 (2): Score $2 imes 1 = 2 < 10$. Count += 1.
• right=1 (1): Score $(2+1) imes 2 = 6 < 10$. Count += 2. (Subarrays: [1], [2, 1]).
• right=2 (4): Score $(2+1+4) imes 3 = 21 \geq 10$.
  • Shrink: remove 2. Score $(1+4) imes 2 = 10 \geq 10$.
  • Shrink: remove 1. Score $4 imes 1 = 4 < 10$.
  • Count += 1. (Subarray: [4]). Total count: 4.

Common mistakes candidates make

• $O(N^2)$ Brute Force: Attempting to calculate every score manually.
• Score Calculation: Forgetting to multiply by the length of the window.
• Integer Overflow: The score can easily exceed $2^{31} - 1$. Always use a 64-bit integer (long in Java/C++, standard integers in Python) for the score and the final count.

Interview preparation tip

Practice identifying "Monotonicity" in subarray problems. If adding an element always moves the condition closer to a limit (like exceeding $k$), then the "Sliding Window interview pattern" is almost certainly the optimal approach.