For those who would like to try it out first! https://leetcode.com/problems/subarray-product-less-than-k/

Question

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Sliding Window Approach

Since this is a contiguous subarray problem, I thought sliding window would be a good approach to take.

Recap on sliding window

With the sliding window approach, the right index is moved until a certain condition is met/not met. Then the left index is shifted until that certain condition stops being true/false. The process continues until the right index reaches the end of the array.

With the example input [10,5,2,6] , here's how the sliding window approach would work out for this question.

left = 0, right = 0, satisfies_condition=True, window = [10], count += 1
left = 0, right = 1, satisfies_condition=True, window = [10,5], count += 2
left = 0, right = 2, satisfies_condition=False, window = [10,5,2]
# trigger shift of left index because satisfies_condition = False
left = 1, right = 2, satisfies_condition = True, window = [5,2], count += 2
left = 1, right = 3, satisfies_condition = True, window = [5,2,6], count += 3
# ends because right == len(array)
return count

However, I was stuck for a very long time on how to come up with the formula for increasing the valid count per window.

I was trying to figure out how to exclude the subarrays that have already been accounted for per step, without having to save all those subarrays in some form.

In my initial approach, if I figure out how to exclude the subarrays that have already been accounted for, I can use the following formula, minus subarrays already been accounted for at each step.

$$\text{Total number of contiguous subarrays} = \dfrac{n * (n+1)}{2}$$

Understanding the count formula in the solution

Eventually, I looked at the solution but I still didn't get it.

Why was the number of unaccounted valid arrays conveniently = the size of the window?

Finally, I understood why!

Using the same example as previously, for [10,5,2,6] and k=100.

Are you starting to see a pattern with the unaccounted subarrays?

...drumroll....

Yes! It's that all of them ends with the rightmost element of the window. And this is key to how we will calculate the unaccounted subarrays at every step.

1) Calculating unaccounted subarrays

The number of subarrays that ends at the right index = (right - left + 1).

Take the valid window [5,2,6] as an example. The possible contiguous subarrays ending at 6 would be [5,2,6] [2,6] [6]. In these subarrays, with a fixed right, the left index moves up by one until it is == right.

So if left = 1 and right = 3, the subarrays we will account for within the window will be when left = 1, left = 2, left = 3. The total number is the same as the size of the window!

2) Proving no overlap in subarrays

Since we are always counting subarrays that end at a different right index, the arrays must be distinct.

And that's why count += window_size at every valid window works :)