Sliding Window : 2

Day 2/75:

Question: Subarray Product Less Than K - (Medium)

Problem Statement : 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.

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.        

Intuition: Our goal is find Count of Subarray whose Product is Less Than target K. By utilizing the sliding window technique, we can dynamically adjust the size of our window to explore different subarrays and find product of each subarray window.

Approach:

Initialization:

• Initialize two pointers, start and end, to mark the boundaries of our window.
• Set the product variable to 1, representing the product of elements within the current window.
• Initialize a count variable to track the number of valid subarrays.

Sliding Window Technique:

• Iterate through the array, advancing the right pointer.
• Update the product by multiplying it with the current element.
• While the product exceeds the target, adjust the window by moving the left pointer and dividing the product by the element at the left pointer.
• Increment the count by the size of the subarray, which is (end- start + 1)..

Result: Return the total count of valid subarrays.

Time Complexity: O(N), where N is the length of the input array. We traverse the array only once with our sliding window, making it a linear time solution.

Space Complexity: O(1) since we use a constant amount of extra space for variables, irrespective of the input size. Hence, our solution is memory-efficient.