713. Subarray Product Less Than K

Problem Statement

Pattern: Pattern Sliding Window

---

Solution

public static int numSubarrayProductLessThanK(int[] nums, int k) {
	// edge case
	if (k == 0) return 0;
	// init
	int start = 0, end = 0, count = 0, currProd = 1;
	// sliding window
	while (end < nums.length) {
		// update currProd
		currProd *= nums[end];
		// currProd > k : increment start and update currProd
		while (currProd >= k && start <= end) currProd /= nums[start++];
		// update count (if start=end+1, count=0)
		count += end - start + 1;
		end++;
	}
	return count;
}

Notes

• Create a sliding window incrementally, where prod of all the elements is less than k.
  • at each increment add size of sliding window to count of subarrays … WHY?
    • number of subarrays for an array of size n = n + n-1 + n-2 + n-3... n(n+1)/2

CONCEPT

Every element added to the front of a subarray forms x sub-arrays with the elements before it, where x is the size of the subarray

• Easier to understand it backwards

  • array of size 4 : [1, 2, 3, 4, 5]
    • no. of subarrays that can be formed with the 4th element are 4
      • 4, 4 3, 4 3 2, 4 3 2 1
    • no. of subs formed with third element : 3
      • 3, 3 2, 3 2 1
    • no. of subs formed with second element: 2
      • 2, 2 1
    • no. of subs formed with first element: 1
      • 1
    • All together the above form all the sub arrays possible

• ‘end-start+1’ unique subarrays can be created with new el at ‘end’