Leetcode: Subarray Product Less Than K

 This question is asked very commonly at Akuna Capital for software developers. It is as follows: 

You are given an array of positive integers nums. Count and print the number of contiguous subarrays where the product of all elements in the subarray is less than k. Here is a description:

So if the product equals to 100, the maximum product this can have is equivalent to 99. Obviously there is an O(n^n) solution but this is inefficient. For example, if there are 5 elements then there are 3,125 possible solutions and for 10 subarrays the number of solutions thus increases to one billion. There has to be a better way.  

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.

We have a product, and a result, which represents the number of contiguous subarrays. 

The approach that we're going to take is a sliding window, and have a left and right subwindow, expanding the right boundary and you move it along the array expanding the left boundary and then move the left foward. It's like a window that starts and it expands the right boundary. When we hit the limit of K, we say we can't do this, and then we start moving the window accross the array whenever we hit that boundary. The result is the right index minus the left index. Another problem that pertains to the sliding window approach is denoted here.

 Here's the final code: 

class Solution {

    public int numSubarrayProductLessThanK(int[] nums, int k) {

        //Base case

        if(k <= 1) return 0; 

        //get product, left and right in sliding window, and return value. 

        int prod = 1;

        int result = 0; 

        int left = 0;

        int right = 0;

        //go to end of substring

        while(right < nums.length) {

            //add an additional element to the product

            prod *= nums[right];

            //change the beginning of the subarray if we reached over the limit k.

            while(prod >= k) {

                prod /= nums[left];

                left++;

            }

            //number of contiguous subarrays. The length is right - left

            result += right - left + 1;

            //increment end. 

            right++;

        }

        return result;

    }

}

We always add the increase in length plus the new element, then we expand the window. 

+1 is for the individual subarray, but expanded by one we add += the number of subarrays that indicates the number of subarrays with the difference. Like it would get all subarrays of an array of [a, b, c, d] with [a] [a, b] [a, b, c] [a, b, c, d] and this is how to increase the number of elements in this particular subarray. Q.E.D.