# 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.
```



### Approach: Sliding Window

1. The idea is always keep an `max-product-window` less than `K`;
2. Every time shift window by adding a new number on the right(`j`), if the product is greater than k, then try to reduce numbers on the left(`i`), until the subarray product fit less than `k` again, (subarray could be empty);
3. Each step introduces `x` new subarrays, where x is the size of the current window `(j + 1 - i)`;\
   example:\
   for window (5, 2), when 6 is introduced, it add 3 new subarray: (5, (2, (6)))

```
    (5, 2, 6)
     (2, 6)
     (6)
```

> **`Time: O(n)                Space: O(1)`**

```python
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1: return 0
        prod = 1
        ans = left = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod /= nums[left]
                left += 1
            ans += right - left + 1
        return ans
```

![](https://2282290372-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MJcwT61yCiz5H4ZddkF%2F-Mg1Qcph8irgoqR4fZSE%2F-Mg1R_7RNHUUQSwb8KA3%2Fimage.png?alt=media\&token=5b67446b-5300-43ec-9e79-3c7a98902a4b)

###

