713. Subarray Product Less Than K.md

713. Subarray Product Less Than K

---

leetcode Daily Challenge on September 28th, 2020.

---

Difficulty : Medium

Related Topics : Array、Two Pointers

---

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.

---

Solution

• mine
  • Java

    • Time Limit Exceeded

      // O(N^2)time
      // O(1)space
      public int numSubarrayProductLessThanK(int[] nums, int k) {
          int n = nums.length;
          int res = 0;
          for(int i = 0; i < n; i++){
              long t = 1;
              for(int j = i; j < n; j++){
                  t *= nums[j];
                  if(t < k){
                      res++;
                  }else break;
              }
          }
          return res;
      }
      

    • Two Pointers Runtime: 10 ms, faster than 31.14%, Memory Usage: 48.5 MB, less than 98.42% of Java online submissions

      // O(N)time
      // O(1)space
      public int numSubarrayProductLessThanK(int[] nums, int k) {
          int res = 0;
          int n = nums.length;
          int l = 0;
          long t = 1;
          for(int i = 0; i < n; i++){
              t *= nums[i];
              while(t >= k && l <= i){
                  res += i - l;
                  t /= nums[l++];
              }
          }
          long r = n - l;
          res += r * (r + 1) / 2;
          return res;
      }
      

---

• the most votes

• Two Pointers Runtime: 6 ms, faster than 100.00%, Memory Usage: 48.9 MB, less than 89.46% of Java online submissions

  // O(N)time
  // O(1)space
  public int numSubarrayProductLessThanK(int[] nums, int k) {
      int res = 0;
      int start = 0;
      int prod = 1;
  
      for (int i = 0; i < nums.length; i++) {
          if (nums[i] >= k) {
              start = i + 1;
              prod = 1;
          } else {
              prod *= nums[i];
              while (prod >= k ) {
                  prod /= nums[start];
                  start++;
              }
              res += i - start + 1;
          }
      }
      return res;
  }
  

---

• the leetcode other solution

• Binary Search Runtime: 99 ms, faster than 5.94%, Memory Usage: 47.8 MB, less than 99.95% of Java online submissions

  // O(N * logN)time
  // O(N)space
  public int numSubarrayProductLessThanK(int[] nums, int k) {
      if (k == 0) return 0;
      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 ans = 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;
          }
          ans += lo - i - 1;
      }
      return ans;
  }
  

---