Your 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.Intuition
\nBecause , we can reduce the problem to subarray sums instead of subarray products. The motivation for this is that the product of some arbitrary subarray may be way too large (potentially 1000^50000), and also dealing with sums gives us some more familiarity as it becomes similar to other problems we may have solved before.
Algorithm
\nAfter this transformation where every value x becomes log(x), let us take prefix sums prefix[i+1] = nums[0] + nums[1] + ... + nums[i]. Now we are left with the problem of finding, for each i, the largest j so that nums[i] + ... + nums[j] = prefix[j] - prefix[i] < k.
Because prefix is a monotone increasing array, this can be solved with binary search. We add the width of the interval [i, j] to our answer, which counts all subarrays [i, k] with k <= j.
Python
\nclass Solution(object):\n def numSubarrayProductLessThanK(self, nums, k):\n if k == 0: return 0\n k = math.log(k)\n\n prefix = [0]\n for x in nums:\n prefix.append(prefix[-1] + math.log(x))\n\n ans = 0\n for i, x in enumerate(prefix):\n j = bisect.bisect(prefix, x + k - 1e-9, i+1)\n ans += j - i - 1\n return ans\n
Java
\nclass Solution {\n public int numSubarrayProductLessThanK(int[] nums, int k) {\n if (k == 0) return 0;\n double logk = Math.log(k);\n double[] prefix = new double[nums.length + 1];\n for (int i = 0; i < nums.length; i++) {\n prefix[i+1] = prefix[i] + Math.log(nums[i]);\n }\n\n int ans = 0;\n for (int i = 0; i < prefix.length; i++) {\n int lo = i + 1, hi = prefix.length;\n while (lo < hi) {\n int mi = lo + (hi - lo) / 2;\n if (prefix[mi] < prefix[i] + logk - 1e-9) lo = mi + 1;\n else hi = mi;\n }\n ans += lo - i - 1;\n }\n return ans;\n }\n}\n
Complexity Analysis
\nTime Complexity: , where is the length of nums. Inside our for loop, each binary search operation takes time.
Space Complexity: , the space used by prefix.
Intuition
\nFor each right, call opt(right) the smallest left so that the product of the subarray nums[left] * nums[left + 1] * ... * nums[right] is less than k. opt is a monotone increasing function, so we can use a sliding window.
Algorithm
\nOur loop invariant is that left is the smallest value so that the product in the window prod = nums[left] * nums[left + 1] * ... * nums[right] is less than k.
For every right, we update left and prod to maintain this invariant. Then, the number of intervals with subarray product less than k and with right-most coordinate right, is right - left + 1. We\'ll count all of these for each value of right.
Python
\nclass Solution(object):\n def numSubarrayProductLessThanK(self, nums, k):\n if k <= 1: return 0\n prod = 1\n ans = left = 0\n for right, val in enumerate(nums):\n prod *= val\n while prod >= k:\n prod /= nums[left]\n left += 1\n ans += right - left + 1\n return ans\n
Java
\nclass Solution {\n public int numSubarrayProductLessThanK(int[] nums, int k) {\n if (k <= 1) return 0;\n int prod = 1, ans = 0, left = 0;\n for (int right = 0; right < nums.length; right++) {\n prod *= nums[right];\n while (prod >= k) prod /= nums[left++];\n ans += right - left + 1;\n }\n return ans;\n }\n}\n
Complexity Analysis
\nTime Complexity: , where is the length of nums. left can only be incremented at most N times.
Space Complexity: , the space used by prod, left, and ans.
Analysis written by: @awice.
\n