LeetCode Daily Problem : 713. Subarray Product Less Than K

Problem Statement:

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.

Example:

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]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Constraints:

• 1 <= nums.length <= 3 * 10⁴
• 1 <= nums[i] <= 1000
• 0 <= k <= 10⁶

Photo by Anastasiia Tarasova on Unsplash

Intuition:

To solve this problem, we can utilize a sliding window approach. We initialize a sliding window represented by two pointers, left and right. We maintain a product variable to keep track of the product of elements within the window. As we move the right pointer to expand the window, we multiply the current product by the number at the right pointer. If the product exceeds or equals k, we shrink the window by moving the left pointer until the product is less than k. At each valid window, the number of subarrays that can be formed is right - left + 1, which we add to the result. By iterating through the array with the right pointer, we count all valid subarrays.

Approach:

1. Initialize variables product, left, and result to 1, 0, and 0, respectively.
2. Iterate through the array with a loop variable right.
3. Update the product by multiplying it with the number at the current right index.
4. While the product is greater than or equal to k and left is less than or equal to right, divide the product by the number at the left index and increment left.
5. If the product is less than k, increment the result by (right - left + 1), representing the number of valid subarrays.
6. Return the final result.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input array nums. This is because we traverse the array once with the sliding window technique.

Space Complexity:

The space complexity is O(1) since we are using only a constant amount of extra space for variables.

Code :

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        pro,l,res=1,0,0

        for r in range(len(nums)):
            pro*=nums[r]

            while pro>=k and l<=r:
                pro/=nums[l]
                l+=1
            
            if pro<k:
                res+=(r-l+1)
            
        return res