Java O(n) with explaination


  • 0
    M
    1. Find the range [i, j), which has the largest subarray production < k
    2. i' = i+1 and divide the largest production with nums[i]
    3. Find the new range [i', j') which has the largest subarray production < k
      and so on...
    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            int ans = 0, right = 0, prod = 1;
            for(int left = 0; left < nums.length; prod /= nums[left], left++){
                // case 1: init state, or
                // case 2: for the case that current number >= k
                if(right <= left){
                    right = left;
                    prod = 1;
                }
                // find the largest subarray production less than k
                while(right < nums.length && prod * nums[right] < k) prod *= nums[right++];
                // update the count of all possible subarrays
                ans += right - left;
                
                // System.out.println(left + "," + right + ", prod = " + prod + ", ans = " + ans);
            }
            return ans;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.