Straightforward Solution


  • 3

    Thanks for @ohazyi and @awice pointing it out. I've updated my code below and it passes all test cases now.

    public int numSubarrayProductLessThanK(int[] nums, int k) {
                if (k < 2) {
                    return 0;
                }
                int result = 0;
                int product = 1;
                for (int i = 0, right = 0; right < nums.length; right++) {
                    product *= nums[right];
                    while (i < nums.length && product >= k) {
                        product /= nums[i++];
                    }
                    result += right - i + 1;
                }
                return result;
            }
    

  • 0

    @fishercoder
    Why this solution won't get TLE if there is 1 of 50000 times and k = 2?


  • 0
    L

    I was trying another O(n^2) solution but was getting TLE.

            if not nums: return 0
            count = 0
            cprod = [1]
            for i in range(0, len(nums)):
                cprod.append(cprod[-1]*nums[i])
            for i in range(0,len(cprod)):
                for j in range(0, i+1):
                    if i!=j:
                        if int(cprod[i]/cprod[j])<k:
                            count+=1
            return count
    

    Then used the same solution as above in python, still getting TLE.

            if not nums: return 0
            count = 0
            for i in range(0, len(nums)):
                prod = nums[i]
                if prod<k: count+=1
                for j in range(i+1, len(nums)):
                    prod*=nums[j]
                    if prod<k:
                        count+=1
                    else:
                        break
            return count
    

  • 1

    @lalib The testcases were recently updated to make N^2 solutions fail, so that might be why you are getting TLE now.


  • 2

    @fishercoder It would be super helpful if you could add a line or two about what the code does. I am pretty sure many newbies (like me) are finding it difficult to understand.


  • 0

    Thanks for your ideas @fishercoder. I tried for a clean version

    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            int count = 0, left = 0, right = 0, prod = 1;
            while(right < nums.length){
                prod *= nums[right++];
                while(prod >= k && left < right)
                    prod /= nums[left++];
                count += right - left; 
            }
            return count;
        }
    }
    

Log in to reply
 

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