713. Subarray Product Less Than K — LeetCode(Python)

I got you!

Problem:

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

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

Constraints:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

Solution:

pro = 1
l, ans = 0, 0
        
for r in range(len(nums)):
    pro *= nums[r]
    while pro >= k and l <= r:
        pro /= nums[l]
        l += 1
    ans += r - l + 1
            
return ans

Explanation —

We use a two-pointer sliding window approach here. l and r are two pointers that initially point to the 0th index of the array nums.

A pro variable is initialized to 1 and it stores the value of the current window’s product.

If the value of pro is greater than or equal to the value of k, we slide the window by shifting the left pointer until this is not the case.

The ans variable stores the length of the windows that satisfy the condition pro ≤ k.

This ans variable is then returned.

Time and Space Complexity —

Since we are iterating over the array once in the outer loop and the inner loop causes us to visit each node at most twice, we can say that our algorithms runs in linear time.

Also, our algorithms requires constant extra space since only a few variables have to be used.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏