Problem Challenge 6: Subarrays with Product Less than a Target (hard)

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!

adi berkowitz

· 2 years ago

I have my own solution that I think is way less complex and similar efficiency.

We have outer loop which is O(N) and then we do an inner loop to get subarrays and we unpack arrays as we add them making the overall time complexity O(N^3)

Space O(N^3)

class Solution:
  def findSubarrays(self, arr, target):
    result = []
    end = len(arr)
    # TODO: Write your code here
    # Go through the entire array
    for i, num in enumerate(arr):
      # Pointer starts after current index (for continuous array)
      pointer = i+1
      product = num
      product_arr = [num]
      # Technically it is possible to have a current number that is more than target
      # But 0 as the next number - this would mean individual target is not but joined it is
      if product < target: