# Subarray Product Less Than K Problem

## Description

LeetCode Problem 713. Given an array of positive integers **nums** and an integer **k**, return the total number of continuous subarrays where the product of all the elements in the subarray is less than **k**.

Example:

1
2
3
4

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].
The subarray [10, 5, 2] is not included as the product of 100 is not strictly less than k.

## Solution

#### Brute Force Approach

A simple solution is to use the `brute force`

approach. We can consider all possible subarrays and check the product of each subarrays with the given integer *k*.

We can use a left pointer *l* and a right pointer *r* to enumerate all possible subarrays. We loop through each integer in the array *nums* with *l*. For each *l*, we iterate with *r* from *l*+1 to the end of the array. In the meantime, we use a *product* variable to record the accumulative product from *l* to *r*. If *product* is less than *k*, we can increase the total count; otherwise, we can keep on searching.

The time complexity of this approach is O(n^{2}),
and the space complexity is O(1).

#### Two Pointer Approach

There are a lot of unnecessary calculation in the above approach. For example, when the *product* is equal to or greater than *k*, we do not need to continue the search for the rest of the array. We can optimize the brute force approach by reducing unnecessary calculations.

We keep two pointers: left *l* and right *r*. We iterate the right pointer through the array. The left pointer starts from the first element. When the *product* of the elements between the two pointers is greater or equal to *k*, we move the left pointer *l* to the right until the *product* is less than *k*. Then the subarrays ending at the element pointed by *r* satisfy the requirement and should be counted (the number of these subarrays is (*r*-*l*+1).

Here is a complete walk through of the `two pointer`

approach. The array *nums* is {10, 5, 2, 6}, and *k* is 100.

1
2
3
4
5
6
7

| nums | product | count |
| 10 | 5 | 2 | 6 | 1 | 0 | Initialization
lr | 10 | 1 | product<100 => count = count+(r-l+1) = 0+(0-0+1) = 1
l r | 50 | 3 | product<100 => count = count+(r-l+1) = 1+(1-0+1) = 3
l r | 100 | 3 | product=100 => product/=nums[l], l++, until product<100
l r | 10 | 5 | product<100 => count = count+(r-l+1) = 3+(2-1+1) = 5
l r | 60 | 8 | product<100 => count = count+(r-l+1) = 5+(3-1+1) = 8

The time complexity can be reduced to O(n), while the space complexity is still O(1).

## Sample C++ Code

This is a C++ implementation of the two pointer approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int product = 1, count = 0;
int l = 0;
for (int r = 0; r < nums.size(); r ++) {
product *= nums[r];
while (product >= k) {
product /= nums[l];
l ++;
}
count += r - l + 1;
}
return count;
}
int main() {
vector<int> nums={10, 5, 2, 6};
int k = 100;
cout << numSubarrayProductLessThanK(nums, k) << endl;
}