Java O(n) solution with brief explaination


  • 1
    T

    The optimizing way is, for subarray start at position i, if the subarray ends at i + 1, i + 2...i + ct - 1 is correct. Then for the next start point i + 1, you don't have to check these ends again, because these subarrays products are all smaller than nums[i] * nums[i+1] * ...* nums[i + ct - 1]. You can directly start from checking the end of i + ct.

    Each element would be considered as start once, and each element would be considered as end once. So it's O(n).

    '''

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int ct = 0;
        int prod = 1;
        int sol = 0;
        for (int i = 0; i < nums.length; i++) {
            if (ct == 0) {
                prod = 1;
            } else {
                ct--;
                prod /= nums[i-1];
            }
            for (int j = i + ct; j < nums.length; j++) {
                if (prod * nums[j] < k) {
                    ct++;
                    prod *= nums[j];
                } else break;
            }
            sol += ct;
        }
        return sol;
    }
    

    '''


Log in to reply
 

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