Solution Problem Challenge 5: : Subarrays with Product Less than a Target

Problem Statement

Given an array with positive numbers and a positive target number, find all of its contiguous subarrays whose product is less than the target number.

Note: This problem is very similar to the previous one. Here, we are trying to find all the subarrays, whereas in the previous problem, we focused on finding only the count of such subarrays.

Example 1:

Input: [2, 5, 3, 10], target=30                                              
Output: [2], [5], [2, 5], [3], [5, 3], [10]

.....

Like the course? Get enrolled and start learning!

Nabeel Keblawi

· 2 years ago

As others have said, this is a sliding window problem rather than two pointers. Using the sliding window pattern, we get O(N^2) instead of O(N^3).

  def findSubarrays(self, arr, target):
    result = []

    # Use a sliding window
    for start in range(0, len(arr)):
      product = 1.0   # reset for every iteration of start pointer
      subArray = []   # reset new subarray

      # Iterate the end pointer from the start pointer until product exceeds target
      for end in range(start, len(arr)):
        product *= arr[end]
        if product >= target:
          break
         
        subArray.append(arr[end])
        result.append(list(subArray))
    
    return result

Show 1 reply