subarray_product_less_than_k.cpp

/**
     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.

    The provided code defines a Java class Solution with a method numSubarrayProductLessThanK that counts the number 
    of subarrays in an input array nums whose product is less than a given threshold k. It uses a sliding window 
    approach to efficiently compute this count.

    Time Complexity:

    The code iterates through the nums array once, using two pointers (startWindow and endWindow) to define the 
    sliding window. This results in a time complexity of O(N), where N is the length of the input array nums.
    Space Complexity:

    The code uses a constant amount of additional space to store integer variables (startWindow, product, and count). 
    Therefore, the space complexity is O(1), which means it is independent of the size of the input array.
 */

#include <vector>

class Solution {
public:
    int numSubarrayProductLessThanK(std::vector<int>& nums, int k) {
        int startWindow = 0; // The left end of the sliding window
        int product = 1;    // Initialize product to 1 to accumulate the product
        int count = 0;      // Count of subarrays with a product less than k

        // Iterate through the array using a sliding window approach
        for (int endWindow = 0; endWindow < nums.size(); endWindow++) {
            // Multiply the current element to the product
            product *= nums[endWindow];

            // Shrink the window by moving the start pointer as long as the product is greater than or equal to k
            while (startWindow <= endWindow && product >= k) {
                // Divide the product by the element at the start of the window
                product /= nums[startWindow];
                // Move the start of the window to the right
                startWindow++;
            }

            // Update the count with the number of valid subarrays within the current window
            count += endWindow - startWindow + 1;
        }

        // Return the count, which represents the number of subarrays with a product less than k
        return count;
    }
};