Problem Statement

Given an array of positive integers nums and an integer k, we are tasked with finding the number of contiguous subarrays where the product of all the elements in the subarray is less than k.

Examples:

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: Contiguous subarrays with a product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Example 2:

Input: nums = [1, 2, 3], k = 0
Output: 0
Explanation: There are no contiguous subarrays with a product less than 0.

What is a Subarray?

A subarray is a contiguous sequence of elements within an array. For example, given an array [1, 2, 3], the subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3]. You need to multiply the elements within the subarray to find the product. Then just count the number of subarrays with a product less than k.

Efficient Two-Pointer Approach:

To efficiently solve this problem, we employ a two-pointer technique. Here's how it works:

• Initialize Variables: We begin by initializing a variable output to keep track of the count of subarrays with a product less than K.
• Iterate Through the Array: We use a pointer i to iterate through the array nums.
• Calculate Product: For each element num at index i, we initialize a variable product to num.
• Inner Loop: We then start another loop with pointer j starting from i to the end of the array.
• Update Product: Within the inner loop, we update the product by multiplying it with the current element nums[j].
• Check Product: If the product exceeds or equals K, we break out of the inner loop.
• Increment Output: We increment the output variable for each subarray with a product less than K.
• Repeat Steps: We repeat steps 3-7 until all subarrays have been processed.
• Return Output: Finally, we return the output count, representing the number of subarrays with a product less than K.

Code

Here's the JavaScript code implementing the two-pointer approach:

var numSubarrayProductLessThanK = function (nums, k) {
    let output = 0 // Initialize output variable to count subarrays with product less than k

    // Iterate through the array nums using pointer i
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i] // Current number at index i
        let product = num // Initialize product with current number

        // Start inner loop with pointer j starting from i to the end of the array
        for (let j = i; j < nums.length; j++) {
            if (i !== j) {
                // If i is not equal to j, update product by multiplying it with the current number
                const otherNum = nums[j]
                product *= otherNum
            }

            // Check if product exceeds or equals k, if so, break out of the inner loop
            if (product >= k) break

            // Increment output for each subarray with product less than k
            output++
        }
    }

    // Return the count of subarrays with product less than k
    return output
}

Complexity Analysis

The time complexity of this approach is O(n^2), where n is the length of the input array nums. This is because we have two nested loops, one iterating through the array and the other starting from the current index to the end of the array.

The space complexity is O(1) as we are using a constant amount of extra space for variables like output, num, product, and otherNum.

If you found this blog post helpful, please like and share it with others. For more such content, you can subscribe to my youtube channel DSA with JS