Sliding Window: Given an array and a target value, get the subarray product less than k

Coding Interview Questions

1 min read

Problem Statement:

Given an array and a target value, get the subarray product less than k

Example:

Input: arr = [1, 2, 4, 3] k = 20

Output: 8

Solution Explanation:

we will solve with the help of sliding window approach.

Keep 2 pointers left and right.

Keep moving right window and if the product becomes greater than or equal to k, shrink the left window until the product becomes less than k.

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

Code Solution

#include <iostream>
#include <vector>
using namespace std;


int solution(vector<int>& nums, int k) 
{
	int left = 0;
	int right = 0;
	int product = 1;
	int result = 0;
	int n = nums.size();

	if(k <= 1) 
		return 0;

	while (right < n) 
	{
	  product *= nums[right];
	  while (product >= k) 
	  	product /= nums[left++];

	  result += 1 + (right - left); // to get the number ending at right

	  right++;
	}
	return result;
}


int main() 
{
    vector<int> arr = {1, 2, 4, 3};
    int k = 20;

    cout << solution(arr, k);
}