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.