Subarray Product Less Than K

Patrick Leaton
Published: June 22, 2021, 7:56 p.m.
Problem Description

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 * 10^4
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 10^6

 

The description was taken from https://leetcode.com/problems/subarray-product-less-than-k/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
       
        left, right = 0, 0
        output, product = 0, 1
       
        while right < len(nums):
            product *= nums[right]
            while product >=k:
                product /= nums[left]
                left += 1
            output += right-left+1
            right += 1
       
        return output

Problem Explanation

The input array has various subarrays that could be multiplied and be less than k.

At first, this seems like a backtracking problem since we are given an exhaustive search requirement.  However, because we need to consider a bunch of different subarrays and quickly backtrack when we get a running product greater than k, we can use a sliding window.  This will allow us to decrease the size of our window in a single iteration instead of needing to wait on a false value to be returned up an entire recursive tree branch.

Like other sliding window problems, we will have a running product count, we will test our window against a condition, if the condition is satisfactory then we will continue to expand our window size.  If the condition is not, we will shrink our window and begin to try a different window.  The only place this question differs from traditional sliding window problems is instead of needing to find a single window, we will be finding all windows.

First off, if we have no k or a negative k, then we would be done because the description says we have no negative numbers.

If that's the case, we will return zero.

        if k <= 1:
            return 0

 

If we do have a k value, we will initialize our left and right pointers to the beginning of our input array.  These will be used to measure our windows later on.

        left, right = 0, 0

 

We will also create variables to track the valid contiguous subarrays, as well as a product for each current window we will use later.

        output, product = 0, 1

 

Then, we will create a loop that will run while we still have numbers in the input array that we haven't considered within our windows.

        while right < len(nums):

 

We can view it like this, our right pointer will be in charge of picking numbers and throwing them into the window.

Our left pointer will be in charge of picking out numbers while we have a window greater than or equal to k, so that we can try to shrink the window to make it valid again.

Let's throw a number into the window and multiply it to our current product.

             product *= nums[right]

 

If the product is less than k, then we can just include this window in the output and continue expanding.

However, if it is not, we will need to start dropping numbers.

As mentioned earlier, at this point, the window is not satisfactory.  We will need to continuously remove the number at the left pointer until our window is less than k.  We will do this by simply dividing the product by the number at the left pointer so we can backtrack on the choice to include it within our window.

Then we will slide the left pointer past the number.

            while product >=k:
                product /= nums[left]
                left += 1

 

Once we have a product of less than k, we will add the window size to the output and continue expanding.

            output += right-left+1
            right += 1

 

This will continue until our right pointer has gone past the end of the array, at which point we have included each valid window.

Now we just need to return the count of windows we found.

        return output