Solution For Subarray Product Less Than K

Problem Statement:

You are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

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].

Solution:

The given problem can be solved by using two pointers approach. The idea is to keep two pointers left and right to represent the left and right boundary of the subarray and then extend the subarray by moving the right pointer until the product of the subarray is less than k. When such a subarray is found, we add the count of subarrays of the current length to the result.

Initially, both the left and right pointers are set to 0. Then, we move the right pointer. For each move of the right pointer, we compute the current product, and check if it is less than k. If it is less than k, then we add the count of subarrays of the current length to the result. We continue to move the right pointer until the product of the subarray exceeds k.

When the product of the subarray exceeds k, we move the left pointer to the right, and update the product by dividing it by the element at the left pointer. We continue to move the left pointer until the product is less than k again. The count of subarrays of the current length is subtracted from the result for each move of the left pointer, since those subarrays do not have a product less than k.

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the input array.

Space Complexity:

The space complexity of the above algorithm is O(1), since we are storing only constant amount of information throughout the algorithm.

Code:

Here is the Python implementation of the above algorithm.

def numSubarrayProductLessThanK(nums, k):
left = 0
right = 0
product = 1
count = 0

while right < len(nums):
    product *= nums[right]
    while product >= k and left <= right:
        product /= nums[left]
        left += 1

    count += (right - left + 1)
    right += 1

return count

Example:

nums = [10,5,2,6] k = 100
print(numSubarrayProductLessThanK(nums, k))

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].

Step by Step Implementation For Subarray Product Less Than K

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) prod /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }
}

/*
Explanation:

We keep track of the running product prod. 
If prod is less than k, we update the answer by adding the number of elements to the right of the current element. 
If prod is greater than or equal to k, we keep dividing prod by nums[left] until it is less than k again. 
The while loop is guaranteed to terminate as prod will eventually become less than or equal to 1.
*/

def subarray_product_less_than_k(nums, k):
    if k <= 1: return 0
    prod = 1
    ans = left = 0
    for right, val in enumerate(nums):
        prod *= val
        while prod >= k:
            prod /= nums[left]
            left += 1
        ans += right - left + 1
    return ans

var subarrayProductLessThanK = function(nums, k) {
    // keep track of number of subarrays with product less than k
    let count = 0;
    
    // iterate through each element in the array
    for (let i = 0; i < nums.length; i++) {
        // product starts at the element at the current index
        let product = nums[i];
        
        // if the product is already greater than k, move to the next element
        if (product >= k) {
            continue;
        }
        
        // otherwise, increment the count for the number of subarrays with product less than k that start with the current element
        count++;
        
        // iterate through the remaining elements
        for (let j = i + 1; j < nums.length; j++) {
            // multiply the product by the element at the current index
            product *= nums[j];
            
            // if the product is greater than or equal to k, break out of the loop
            if (product >= k) {
                break;
            }
            
            // otherwise, increment the count for the number of subarrays with product less than k that start with the current element
            count++;
        }
    }
    
    // return the total count
    return count;
};

class Solution {
public:
    int numSubarrayProductLessThanK(vector& nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.size(); right++) {
            prod *= nums[right];
            while (prod >= k) prod /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }
};

using System; 

public class Solution { 
    public int NumSubarrayProductLessThanK(int[] nums, int k) { 
        if (k <= 1) return 0; 
        int prod = 1, ans = 0, left = 0; 
        for (int right = 0; right < nums.Length; right++) { 
            prod *= nums[right]; 
            while (prod >= k) prod /= nums[left++]; 
            ans += right - left + 1; 
        } 
        return ans; 
    } 
}