5-liner O(N) time and O(1) space, two pointers

  • 0

    Let prod keep tracking the product of nums[i:j]. Note that whenever prod < k, we have (j-i+1) extra qualified contiguous arrays than in previous range nums[i,j-1], i.e., those (j-i+1) arrays ending with nums[j].

        int numSubarrayProductLessThanK(vector<int>& nums, int k) 
            int count = 0;
            if (k > 1)
              for (int i = 0, j = 0, prod = 1; j < nums.size(); count += (j++ -i+1)) 
                for (prod *= nums[j]; prod >= k; ++i) prod /= nums[i];
            return count;

Log in to reply

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