# Explanation

`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.`
`idx = 0:monotonic_queue = [10], good, ret += len(monotonic_queue)idx = 1:monotonic_queue = [10, 5], good, ret += len(monotonic_queue)idx = 2:monotonic_queue = [10, 5, 2], bad, popleftmonotonic_queue = [5, 2], good, ret += len(monotonic_queue)idx =  3:monotonic_queue = [5, 2, 6], good, ret += len(monotonic_queue)`

# Solution

`"""Time complexity: O(n)Space complexity: O(n), the worst case, all the elements of nums will be put into the monotonic_queue"""class Solution:    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:        monotonic_queue = collections.deque([])        prod , ret = 1, 0        for num in nums:            prod *= num            monotonic_queue.append(num)            while monotonic_queue:                if prod < k:                    break                else:                    prod //= monotonic_queue.popleft()            ret += len(monotonic_queue)        return ret`

## C++ code

`class Solution {public:    int numSubarrayProductLessThanK(vector<int>& nums, int k) {        if (k == 0) return 0;        int ret = 0, product = 1;        deque<int> dq;        const int n = nums.size();        for (int i = 0; i < n; ++i)         {            product *= nums[i];            dq.push_back(i);            while (!dq.empty() && product >= k) {                auto j = dq.front(); dq.pop_front();                product /= nums[j];            }            ret += dq.size();        }        return ret;    }};`
`class Solution {public:    int numSubarrayProductLessThanK(vector<int>& nums, int k) {        if (k == 0) return 0;        int ret = 0, product = 1;        const int n = nums.size();        int j = 0;        for (int i = 0; i < n; ++i)         {            product *= nums[i];            while (j <= i && product >= k)             {                 product /= nums[j++];            }            ret += i - j + 1;         }        return ret;    }};`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.