Subarray Product Less Than K LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Facebook LinkedIn MicrosoftViews 5442

Problem Statement

Subarray Product Less Than K LeetCode Solution – Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example

Test Case 1:

Input:

inputArr = [10, 5, 2, 6]

k = 100

Output:

8

Test Case 2:

inputArr = [1,2,3]
k = 0

Output:

0

Explanation for Subarray Product Less Than K LeetCode Solution:

i) for the 1st test case, the subarrays having product less than 100 are: [10], [5], [2], [6], [10. 5], [5, 2], [2, 6], [5, 2 ,6]. So total count is 8.

ii) for the 2nd test case, there is no subarray having product less than 0. So the output is 0.

Approach

  1. Idea is to make a window with a product less than k .
    left: The starting point of the window
    Right: Pointer that is going to traverse the array (or end of window)
  2. After including A[right] there are 2 Cases Possible:

    CASE 1: product is less than k
    It means that I can be part of previous Subarrays (right-left) and also can start a subarray from me(+1).
    So in total Subarrays increase count by (right-left+1)

    CASE 2:Product will become greater than k
    Start releasing element from left till product will become less than k.
    Now same logic as of Case 1.

    As per the given constraint: k>=0 and values in the array can be in b/w 0 to 1000.
    As we want subarrays whose products are strictly less than k.
    so if(k<=1) return 0.
    and luckily here you don’t have the problem that the product of number is exceeding the Integer.Max Range.

Idea:

  1. The idea is always to keep a max-product-window less than k;
  2. Every time shift window by adding a new number on the right(j), if the product is greater than k, then try to reduce numbers on the left(i), until the subarray product fit less than k again, (subarray could be empty);
  3. Each step introduces x new subarrays, where x is the size of the current window (j-i+1).

It’s basically a variable-size sliding window problem.

Code

Java Program

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) return 0;
        int cnt = 0;
        int pro = 1;
        for (int i = 0, j = 0; j < nums.length; j++) {
            pro *= nums[j];
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;        
    }
}

C++ Program

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int cnt = 0;
        int pro = 1;
        for (int i = 0, j = 0; j < nums.size(); j++) {
            pro *= nums[j];
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;
    }
};

Python Program

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k == 0:
            return 0
        start, prod, cnt = 0, 1, 0
        for end in range(len(nums)):
            while start <= end and prod*nums[end] >= k:
                prod = prod/nums[start]
                start += 1
            prod = 1 if start > end else prod*nums[end]
            cnt = cnt if start > end else cnt+(end-start+1)
        return cnt

Complexity Analysis for Subarray Product Less Than K LeetCode Solution

Time Complexity

, where N is the length of nums. left can only be incremented at most N times.

Space Complexity

The space complexity of the above code is O(1), the space used by prod, left, and ans.

Reference: https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples

Translate »