# Monotonic queue

713. Subarray Product Less Than K

# Problem

713. Subarray Product Less Than K

# General explanation about the Monotonic queue

The monotonic queue is very elegant, usually, it can give us a very elegant O(n) time complexity solution. Here are several of my opinions:

- Monotonic queue problems are harder than DP problems
- The monotonic queue is commonly used for subarray related problems.
- A very classical one is finding the min/max value in a sliding window. See My previous article HERE.

# Explanation

We can use a monotonic queue to solve this problem, the basic idea can be demonstrated as follows:

**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.

Use the example in the problem description

`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, popleft

monotonic_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;

}

};

We can also use two pointer to solve this problem

`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;

}

};

Thanks for reading.