Subarray Product Less Than K

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 = 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

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! 🙂