Subarray Product Less Than K

---

Subarray Product Less Than K: 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

---

Try this Problem on your own or check similar problems:

1. Maximum Product Subarray
2. Number of Smooth Descent Periods of a Stock
3. Count Subarrays With Score Less Than K

Solution:

Java

public int numSubarrayProductLessThanK(int[] nums, int k) {
  int count = 0, i = 0, j = 0, currentProduct = 1;

  while(j < nums.length){
      currentProduct *= nums[j];
      while(currentProduct >= k && i <= j){
        currentProduct /= nums[i];
        ++i;
      }
      count += j - i + 1;
      ++j;
  }

  return count;
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function (nums, k) {
  let count = 0;
  let i = 0;
  let j = 0;
  let currentProduct = 1;

  while (j < nums.length) {
    currentProduct *= nums[j];
    while (currentProduct >= k && i <= j) {
      currentProduct /= nums[i];
      i += 1;
    }
    count += j - i + 1;
    j += 1;
  }

  return count;
};

Python

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        count = 0
        i = 0
        j = 0
        currentProduct = 1

        while j < len(nums):
            currentProduct *= nums[j]
            while currentProduct >= k and i <= j:
                currentProduct /= nums[i]
                i += 1
            count += j - i + 1
            j += 1

        return count

C++

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int count = 0;
        int i = 0;
        int j = 0;
        int currentProduct = 1;

        while (j < nums.size()) {
            currentProduct *= nums[j];
            while (currentProduct >= k && i <= j) {
                currentProduct /= nums[i];
                i += 1;
            }
            count += j - i + 1;
            j += 1;
        }

        return count;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We can use two pointer approach (or sliding window) approach here and move the pointer j until we encounter an invalid window (currentProduct >= k) in that case we have to decrease our product so we divide it with element on the start of our window (to which i is pointing) and we do that until we have a valid window again (currentProduct < k). The tricky part is how do we increase the count for each valid window? Note that for each valid window when we have a new end (we increased j) we get a new subarray (range i..j) which product is lesser than k, but how many new valid subarray are actually created? Well we have the following valid subarrays i..j, i+1..j, i+2..j, ...,j..j, so we have j-i+1 valid subarrays which we add to the total count. We have linear time complexity since we traverse the whole input array at most once.