Subarray Product Less Than K

Problem Statement

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

Try here before watching the video.

Similar Problem

Video Solution

Java Code

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k <= 1) return 0;
        
        int start = 0, subarrayCount = 0;
        int product = 1;

        for(int end = 0; end < nums.length; end++) {
            product *= nums[end];
            while(product >= k) {
                product /= nums[start];
                start += 1;
            }
            subarrayCount += (end - start + 1);
        }

        return subarrayCount;
    }
}

C++ Code

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k <= 1) return 0;
        
        int start = 0, subarrayCount = 0;
        int product = 1;

        for(int end = 0; end < nums.size(); end++) {
            product *= nums[end];
            while(product >= k) {
                product /= nums[start];
                start += 1;
            }
            subarrayCount += (end - start + 1);
        }

        return subarrayCount;
    }
};

Python Code

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        
        start = 0
        subarray_count = 0
        product = 1

        for end in range(len(nums)):
            product *= nums[end]
            while product >= k:
                product /= nums[start]
                start += 1
            subarray_count += (end - start + 1)

        return subarray_count

Javascript Code

var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;
    
    let start = 0;
    let subarrayCount = 0;
    let product = 1;

    for (let end = 0; end < nums.length; end++) {
        product *= nums[end];
        while (product >= k) {
            product /= nums[start];
            start += 1;
        }
        subarrayCount += (end - start + 1);
    }

    return subarrayCount;
};

Go Code

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }
    
    start := 0
    subarrayCount := 0
    product := 1

    for end := 0; end < len(nums); end++ {
        product *= nums[end]
        for product >= k {
            product /= nums[start]
            start += 1
        }
        subarrayCount += (end - start + 1)
    }

    return subarrayCount
}

Complexity Analysis

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