Formatted question description: https://leetcode.ca/all/713.html

Level

Medium

Description

You are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is 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.

Note:

0 < nums.length <= 50000.
0 < nums[i] < 1000.
0 <= k < 10^6.

Solution

Initialize product = 1, count = 0, start = 0 and end = 0. Loop over nums using end as the index. Each time let product *= nums[end]. If product >= k, then do product /= nums[start++] until product < k. Then calculate the length of the current subarray, which is end - start + 1. The length of the current subarray is also the number of subarrays with product less than k and ends at index end. Add the length of the current subarray to count. Finally, return count.

Java Code

public class Subarray_Product_Less_Than_K {

    public static void main(String[] args) {
        Subarray_Product_Less_Than_K out = new Subarray_Product_Less_Than_K();
        Solution s = out.new Solution();

        System.out.println(s.numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100));
    }

    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            if (k == 0) {
                return 0;
            }

            // log transformation: log(a*b) = log(a) + log(b)
            double logk = Math.log(k);
            double[] prefix = new double[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                prefix[i+1] = prefix[i] + Math.log(nums[i]);
            }

            int count = 0;
            for (int i = 0; i < prefix.length; i++) {
                int lo = i + 1, hi = prefix.length;
                while (lo < hi) {
                    int mi = lo + (hi - lo) / 2;
                    if (prefix[mi] < prefix[i] + logk - 1e-9) {
                        lo = mi + 1;
                    } else {
                        hi = mi;
                    }
                }
                count += lo - i - 1;
            }
            return count;
        }
    }


    // this is just a flip, instead of compare for <k, to compare >=k then count.
    // I don't like this one, seems hack. Will still fail according to input
    // what if test case is [9,9,9, ... ,9] (many) and k=1
    class Solution_ACed {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            if (k < 2) {
                return 0;
            }
            int result = 0;
            int product = 1;
            for (int i = 0, right = 0; right < nums.length; right++) {
                product *= nums[right];
                while (i < nums.length && product >= k) {
                    product /= nums[i++];
                }
                result += right - i + 1;
            }
            return result;
        }

    }


    /*
        failed by:
        nums=[1,1,1,1,1, ... ,1] (billion 1s)
        k=9
     */
    class Solution_wrong {

        public int numSubarrayProductLessThanK(int[] nums, int k) {

            if (nums == null || nums.length == 0) {
                return 0;
            }

            int count = 0;

            int left = 0;

            // basic idea, moving right to right direction, if current multiple is >= k , then no need to go right further
            // assumption: all positive
            // variation of this question, what if there is 0, or negative numbers
            while (left < nums.length) {

                int current = 1;
                int right = left;

                // @note: possible overflow from * operation
                while (right < nums.length && current * nums[right] < k) { // will stop if current >= k
                    count++;

                    current *= nums[right];
                    right++;
                }

                left++;
            }

            return count;
        }
    }
}

// OJ: https://leetcode.com/problems/subarray-product-less-than-k/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& A, int k) {
        if (k == 0) return 0;
        long i = 0, j = 0, N = A.size(), prod = 1, ans = 0;
        for (; j < N; ++j) {
            prod *= A[j];
            while (i <= j && prod >= k) prod /= A[i++];
            ans += j - i + 1;
        }
        return ans;
    }
};

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        N = len(nums) # 数组/字符串长度
        left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
        prods = 1 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
        res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
        while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
            prods *= nums[right] # 增加当前右边指针的数字/字符的求和/计数
            while prods >= k and left <= right: # 此时需要一直移动左指针，直至找到一个符合题意的区间
                prods /= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
                left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
            # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
            res += right - left + 1 # 需要更新结果
            right += 1 # 移动右指针，去探索新的区间
        return res

Java

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 1)
            return 0;
        int product = 1;
        int count = 0;
        int start = 0, end = 0;
        int length = nums.length;
        while (end < length) {
            product *= nums[end];
            while (product >= k) {
                product /= nums[start];
                start++;
            }
            count += end - start + 1;
            end++;
        }
        return count;
    }
}

// OJ: https://leetcode.com/problems/subarray-product-less-than-k/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& A, int k) {
        if (k == 0) return 0;
        long i = 0, j = 0, N = A.size(), prod = 1, ans = 0;
        for (; j < N; ++j) {
            prod *= A[j];
            while (i <= j && prod >= k) prod /= A[i++];
            ans += j - i + 1;
        }
        return ans;
    }
};

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        N = len(nums) # 数组/字符串长度
        left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
        prods = 1 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
        res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
        while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
            prods *= nums[right] # 增加当前右边指针的数字/字符的求和/计数
            while prods >= k and left <= right: # 此时需要一直移动左指针，直至找到一个符合题意的区间
                prods /= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
                left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
            # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
            res += right - left + 1 # 需要更新结果
            right += 1 # 移动右指针，去探索新的区间
        return res

713 - Subarray Product Less Than K

Level

Description

Solution

All Problems

All Solutions