713. Subarray Product Less Than K

Problem

General explanation about the Monotonic queue

  • 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

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.

Data Scientist/MLE/SWE @takemobi