Table of Contents

Leetcode 713. Subarray Product Less Than K

##### 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 = 100Output:8Explanation: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 = 0Output:0

**Constraints:**

`1 <= nums.length <= 3 * 10`

^{4}`1 <= nums[i] <= 1000`

`0 <= k <= 10`

^{6}

Source : Leetcode 713. Subarray Product Less Than K

##### Solution

###### A naive approach

The simplest way to think of this problem is taking cumulative product from an index up to the end of the array. Then check if any of those products < k or not. We will have to do this for each index. Then, for any subarray product < k, we can count the number of subarrays and find the result by adding up those counts.

But this approach will cost us O(N2) [O N square] runtime which is not efficient and we don't want that! So, let's not waste time on it. If you want, you can think of it and even try it to some coding practice. No harm in doing that if you have enough time, right?

###### A better approach: Sliding Window

The naive approach is not so bad as we might think of. At least it will help us to provoke thought for the better approach which we will show in a moment.

Like naive approach, we will still take cumulative product but **only from the beginning** of the array!

Okay, but how it will help?

We can have two indices **left** and **right**. The **right** index will move forward and we keep calculating the cumulative product. While at some point the product is >= k, we will move forward **left** pointer (or index). Before moving that, we will divide product by the value pointing by the **left** index.

*(If this sounds little confusing so far, don’t worry, we will see more clearly using images below)*

That’s how we can get the **product < k** and corresponding windows (i.e. gap between **left** and **right** index). But, our job is to count all the subarrays (or windows) having this property. We can add up **1 + the gap** between **left** and **right **index to find that.

But why adding up **1 + the gap** between **left** and **right** index gives the number of subarrays? You can think about that, but we will explain this part later in this blog. For now, accept the fact that it works somehow!

Let’s see how the sliding window will work with the help of images.

Imagine we have an input array as below, **left** and **right** index pointing to the first element of the array (**left = 0**, **right = 0**). A product variable **prod **initialized by 1, and k = 100. We also have a variable **ans** = 0 to keep the result.

Our **right** index will move forward and we will take product along the way of moving. So, as the image below, the first element is 10 (pointed by the **right** index) and the product is updated to 10.

The answer is 1 + current gap between **right** and **left** index position which is 1 + right – left = 1 + 0 – 0 = 1.

In the next step, **right** index is already moved forward by one position. So, **prod** will be updated as **prod = prod * 5**. Other values will be updated same way as before shown in the image below.

Now at this stage, **right** is pointing to 2. Variable **prod** is updated to 100. Now we have a problem, because **prod** is not less than k! This situation violates the condition of a valid subarray for this problem. So, we need to reduce the value of **prod**. The only way to do that is to divide **prod** by the element pointed by **left** and move **left** forward. At this point, we are not moving **right** anymore. **right** index will move only when again **prod < k**.

After moving **left** to its next element, we have **prod** as below image.

Now, **right** will move as below image and we again find prod is not < k. So, we will move **left** again and update **prod**.

Even after moving **left**, we still have **prod** is not < k ! (as below image) So, move **left** more until we find prod < k.

Now, we find the condition is met. So, we update all values as below image and move **right** forward.

Again, the conditions is break and we should move **left** forward.

Finally, the condition is met again and we update all values as below image.

Now, we cannot move **right** anymore. So, the program will end.

###### Q: How do summing up gap between “right” and “left” index gives the number of subarrays?

The key to think about this idea is : **Think right to left**!

Let’s say we have an array as below. We have **k = 10000**. We can easily see that all the subarrays of this array has **prod < k**.

So, for each element of the array, we should calculate number of subarrays, right?

Let’s start from the first element. Here both **left** and **right** are pointing to index 0 and there is only one element. So, the formula of 1 + right – left works intuitively.

Now, let’s move on to the next element. We can find two subarrays now. They are **[1, 2]** and **[2]**.

If we **“Think right to left**“, we can find these subarrays by taking **2** (the second element) and move towards right and appending each element to its left.

For example, we take **2** and make an array **[2]**. Then we go towards left and find 1 and append 1 in the first array. That’s how we get **[2, 1]** which is same as **[1, 2]**.

Similarly, from value **3** (**index 2**), we can append one element towards left and get the subarrays **[2]**, **[2, 3]** and **[1, 2, 3]**. Since we are appending elements from right to left, the **gap** between right and left represents number of elements between right and left. To include the starting element (3), we should add 1 with the **gap**.

Hope the idea is explained. Below image is the final step to find number of subarrays between **0** and **3** index.

##### Code

/* foolishhungry.com Leetcode 713. Subarray Product Less Than K */ class Solution { public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { if(k <= 1) return 0; long long prod = 1; int length = nums.size(); int left = 0; int ans = 0; for(int right = 0; right < length; right++){ prod *= nums[right]; while(prod >= k){ prod /= nums[left]; left += 1; } ans += right - left + 1; } return ans; } };

##### Conclusion

Hope you enjoyed this post. If you do, please write your feedback in the comment. If you did not enjoy, please write about your anger, frustration as well! We are always open to any kind of feedback.

Happy coding! 🙂