This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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 = 100Output:8Explanation: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`

.b'

\n\n#### Approach #1: Binary Search on Logarithms [Accepted]

\n\n\n

\n#### Approach #2: Sliding Window [Accepted]

\n\n\n

\n

'
**Intuition**

Because , 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**

After 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**

class 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**

class 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**

- \n
- \n
Time Complexity: , where is the length of

\n`nums`

. Inside our for loop, each binary search operation takes time. \n - \n
Space Complexity: , the space used by

\n`prefix`

. \n

\n

**Intuition**

For 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**

Our 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**

class 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**

class 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**

- \n
- \n
Time Complexity: , where is the length of

\n`nums`

.`left`

can only be incremented at most`N`

times. \n - \n
Space Complexity: , the space used by

\n`prod`

,`left`

, and`ans`

. \n

\n

Analysis written by: @awice.

\n