Count The Number Of Good Subarrays - Leetcode Solution

Problem Description:

Given an array of integers nums, return the number of contiguous subarrays where the product of all the elements in the subarray is less than k.

Example:

Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays that have a product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

Solution:

The main idea of this problem is to use the sliding window technique to find all the subarrays whose product is less than k. Let's see how we can solve this problem.

1. Initialize left variable to 0 and right variable to 0.
2. Initialize a variable named product to 1.
3. Initialize a variable named count to 0.
4. Iterate the array using the right pointer and calculate the product of the current subarray by multiplying the product with the current element.
5. If the product is greater than or equal to k, then we need to move the left pointer until the product becomes less than k. While doing this, divide the product by nums[left] and increment the left pointer.
6. The number of subarrays whose product is less than k will be the difference between the left and right pointers. Add this count to the variable named count.
7. Finally, return the variable named count.

Let's see the above algorithm in code:

int numSubarrayProductLessThanK(vector<int>& nums, int k) { int n = nums.size(); int left = 0, right = 0, product = 1, count = 0; while (right < n) { product *= nums[right]; while (left <= right && product >= k) { product /= nums[left]; left++; } count += right - left + 1; right++; } return count; }

Time Complexity: O(N) Space Complexity: O(1)

In the above solution, we are iterating the array only once. Hence, the time complexity of the above solution is O(N). We are using constant extra space to store the variables, hence the space complexity of the above solution is O(1).

Conclusion:

The sliding window technique is a very powerful algorithmic technique that can be used to solve various problems. In this problem, we have used this technique to find the number of subarrays whose product is less than k.

1