Two Pointers: Given a array and a value k, return the number of subarray whose product is less that k

Problem Statement:

Given a array and a value k, return the number of subarray whose product is less that k

Example:

Input: nums = [1, 2, 3, 4, 5] k = 8
Output: 8

Explanation:

[1], [2], [3], [4], [5], [1, 2], [2, 3]

Solution 1: Sliding window along with two pointer approach

We maintain a window [left,right] such that the product is less than k.

Expand from right side and if the product is more than k, then shrink from left.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int solution(vector<int>& nums, int k) 
{

    int left = 0;
    int prod = 1;
    int count = 0;

    for(int right=0; right<nums.size(); right++)
    {
        prod *= nums[right];

        while(prod >= k)
        {
            prod /= nums[left];
            left++;
        }

        count += (right-left+1);
    }

    return count;
}

int main() {
    vector<int> num =  {1, 2, 3, 4, 5};
    int k = 8;
   
    cout << solution(num, k)<<endl;
    
    return 0;
}

Output

8