consider the following problem :-

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:

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.

The solution for this using the sliding window method is:-

public class Main {
    public static void main(String[] args) {
        int arr[] = {10, 5,2, 6};
        int k = 100;

        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < arr.length; right  ) {
            prod *= arr[right];
            while (prod >= k) prod /= arr[left  ];
            ans  = right - left   1;
        }
        
        System.out.println(ans);
    }
}

Here is my quesstion:- right - left -1 gives the total number of elements in the subarray extracted then how is this correctly calculating the total number of subarrays possible?

ie: for an array [10, 5, 2, 6]

right=0; left=0; (right-left 1)=1; list=[10]
right=1; left=0; (right-left 1)=2; list=[10, 5]
right=2; left=1; (right-left 1)=2; list=[5, 2]
right=3; left=1; (right-left 1)=3; list=[5, 2, 6]

What is the logic behind calculating the number of elements in the subarray while traversing the array will get the total number of subarrays possible with product less than K ?

CodePudding user response：

You should first figure out what the invariant of the for loop is. In each iteration of the for loop, it fixes a right, and finds the leftmost left such that the range [left, right] contains elements that have a product closest but not exceeding 100, for that particular value of right.

For example, in the last iteration, the range found was [1, 3], and the subarray with that range was [5, 2, 6]. Notice that if we included one more element from the left, the product would be equal to, or exceed 100. You can think of this as finding the longest subarray ending at right that has a product less than 100.

Assuming the integers are all positive, then if we know the longest subarray ending at right that satisfy this condition, we also know that any shorter subarrays ending at right will also satisfy this condition. There are exactly (right - left) shorter subarrays than the longest that we found. Hence, every time we find a left, we count (right - left), plus the longest one we found. This will be the total number of subarrays that end at right that satisfy the condition.

Since the for loop checks every possible ending location (right) for a subarray, and we counted all the subarrays that satisfy the condition for each ending location, we have counted all the subarrays that satisfy the condition.