Introduction:

In certain scenarios, we encounter problems that require us to find the number of contiguous subarrays with a product less than a given number k. This article presents an optimized solution to efficiently solve this problem. We will discuss the approach, code implementation, time and space complexities, and conclude with the advantages of this optimized solution.

Problem Statement:

Given an array of positive numbers, the task is to find the number of possible contiguous subarrays having a product less than a given number k.

Approach:

To solve this problem optimally, we can utilize the sliding window technique. The main idea is to maintain a sliding window of elements and update the product dynamically. Here are the steps involved in the optimized solution:

Initialize variables:

We initialize the variables count, product, and left to 0. count will store the count of subarrays, product will keep track of the current product of the elements in the sliding window, and left will represent the left boundary of the window.
Iterate through the array:

We iterate through the array using the right pointer. At each iteration, we multiply the product by the current element a[right].
Adjust the window:

If the product is greater than or equal to k, we need to adjust the window. We divide the product by the element at the left index and increment left by 1. We repeat this step until the product is less than k.
Update the count:

After adjusting the window, we update the count by adding the size of the subarray, which is right - left + 1. This represents the number of subarrays ending at the current position right with a product less than k.
Return the count:

Finally, we return the count, which represents the total number of contiguous subarrays with a product less than the given number k.

#User function Template for python3

class Solution:
    def countSubArrayProductLessThanK(self, a, n, k):
        if k <= 1:
            return 0

        count = 0
        product = 1
        left = 0

        for right in range(n):
            product *= a[right]

            while product >= k:
                product /= a[left]
                left += 1

            count += right - left + 1

        return count

Time Complexity:

The optimized solution has a time complexity of O(n), where n is the size of the input array. This is because we traverse the array once using the sliding window approach, visiting each element once.

Space Complexity:

The space complexity of this solution is O(1) as we use only a constant amount of extra space to store the variables count, product, and left. The space requirement does not depend on the size of the input array.

Problem Link:

click me

Conclusion:

The optimized solution presented in this article efficiently solves the problem of counting the number of contiguous subarrays with a product less than a given number k.

By utilizing the sliding window technique, we maintain a dynamic window and update the product to achieve linear time complexity. Additionally, the solution uses only constant extra space, making it highly efficient in terms of space complexity. By applying this optimized solution, we can effectively solve similar problems that require counting subarrays with specific conditions.

Happy Coding ✨

DSA Blog