◻️713. Subarray Product Less Than K (medium)

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

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.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

---

Solutions

Brute Force

Generate all sub arrays - T.C -> O(n^2)

Optimised (Sliding Window) using While loop - Std. Soln

Runtime 54 ms Memory 64.03 MB

T.C -> O(2n) -> O(n)

// T.C -> O(2n) -> O(n)
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k < 1) return 0;
        int n = nums.size();
        int l = 0, r = 0, cnt = 0;
        long long mult = 1;

        while (r < n) {
            //sliding window expansion
            mult = mult*nums[r];
            //sliding window shrinking
            while (mult >= k && l <= r) {
                mult = mult/nums[l];
                ++l;
            }

            cnt = cnt + (r-l+1); //if in above while loop if l=r then l++ will happen and automatically (r-l+1) = 0
            ++r;
        }

        return cnt;
    }
};

Optimised (Sliding Window) using For loop

Runtime 60 ms Memory 64.04 MB

T.C -> O(2n) -> O(n)

// T.C -> O(2n) -> O(n)
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0; // prod should be strictly lesser than k
        int n = nums.size();
        int l = 0, r = 0, cnt = 0;
        long long mult = 1;

        for(int r=0; r<n; ++r){         // r=0
            mult = mult*nums[r]; // Sliding window expansion phase   // mult=1*1
            // Sliding Window (shrinking)
            while(mult>=k && l<=r){     //(1>=1 && 0<0){
                mult = mult/nums[l];        // mult = 1/1
                ++l;                        // l=1
            }                           //}   
            cnt += r-l+1;     // Sliding window - valid window operation          
        }
        return cnt;
    }
};