713. Subarray Product Less Than K

二刷 06/2022

Version #1 Two Pointers

We can use two pointers is because all numbers are positive so that the product is increasing while we expand the length of subarray

Time O(N)

Space O(1)

Runtime: 11 ms, faster than 18.84% of Java online submissions for Subarray Product Less Than K.

Memory Usage: 68.9 MB, less than 60.76% of Java online submissions for Subarray Product Less Than K.

class Solution {

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

        long product = 1l;

        int count = 0;

        int slow = 0;

        // product is the product of all nums in subarray [slow, fast]

        for (int fast = 0; fast < nums.length; fast++) {

            product *= nums[fast];

            while (slow <= fast && product >= k) {

                product /= nums[slow];

                slow++;

            }

            count += fast - slow + 1;

        }

        return count;

    }

}

一刷

Two Pointers
key point: result set can be empty

beats 73.08 % 

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int left = 0;
        int right = 0;
        // [left, right]
        int product = 1;
        int result = 0;
        while (right < nums.length) {
            product *= nums[right];
            while (product >= k && left <= right) {
                product /= nums[left++];
            }
            // Result Set can be empty
            result += right - left + 1;
           
            // System.out.println(left + " " + right + " " + result);
            right++;
        }
        return result;
    }
}