Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Solution: Problem Challenge 6: 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!

tahriris

· 2 years ago

Given that the optimal runtime is quadratic, why not just use nested for-loops?

def find_subarrays(arr, target):
    subarrays = []
    for i in range(len(arr)):
        product = 1
        for j in range(i, len(arr)):
            product *= arr[j]
            if product >= target:
                break
            subarrays.append(arr[i : j + 1])
    return subarrays

Show 1 reply

adi berkowitz

· 2 years ago

Much simpler python solution - Instead of backtracking from right to left in the middle, we simply move left over 1 and start again. It is the same exact thing.

class Solution:
  def findSubarrays(self, arr, target):
    result = []
    end = len(arr)
    left = 0
    product = 1
    while left < end:
      product = 1
      right = left
      temp_list = []
      while right < end and arr[right] * product < target:
        temp_list.append(arr[right])
        result.append(list(temp_list))
        product *= arr[right]
        right += 1
      left += 1
    return result

Show 1 reply

softest mike

· 2 years ago

class Solution:
  def findSubarrays(self, arr, target):
    result = []
    n = len(arr)
    for i in range(n):
      subarray_starting_at_i = []
      curr_subarr_i = []
      if arr[i] < target:
        curr_subarr_i.append(arr[i])
        subarray_starting_at_i.append(curr_subarr_i.copy())
        product = arr[i]

        for j in range(i+1, n):
          product = product * arr[j]
          if product < target:
            curr_subarr_i.append(arr[j])
            subarray_starting_at_i.append(curr_subarr_i.copy())
          else:
            break
        result.extend(subarray_starting_at_i)
      else:
        continue

    return result

Show 2 replies

Zachary Nelson

· 2 years ago

I have a slightly different approach which I believe is O(n^2) time complexity, I imagine the space complexity is the same O(n^3) but correct me if I'm wrong.

class Solution {
  findSubarrays(arr, target) {
    let result = [];
    let l = 0;
    let r = 0;
    let runningSum = 1;

    while (r <= arr.length) {
      runningSum *= arr[r];
      
      if (runningSum < target) {
        result.push(arr.slice(l, r + 1));
        r++
      } else {
        l += 1
        runningSum = 1;
        r = l
      }
    }

    return result;
  }
}

Show 1 reply

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 2 replies

Eric Imho Jang

· 2 years ago

class Solution:
  def findSubarrays(self, arr, target):
    result = []
    
    for i in range(len(arr)):
      left = i
      right = i
      product = 1

      while product < target:
        print(left, right, result)
        if left == right and arr[left] < target:
          result.append([arr[left]])
          right += 1
        elif left < right and right < len(arr):
          start = left
          end = right+1
          
          product = 1
          for i in range(start, end):
            product *= arr[i]
          
          if product < target:
            result.append(arr[start:end])
            right += 1
          else:
            break
        else:
          break
          
    return result

lejafilip

· 2 years ago

Abdullah AlKheshen

· 2 years ago

Mohammed Dh Abbas

· 2 years ago

This is a better O(N)^2 solution . the official solution is not ideal and confusing .

Simply do a double loop as below

 def findSubarrays(self, arr, target):
    result = []
    for i in range(len(arr)):
      if arr[i] < target:
        result.append([arr[i]])

      mpy = arr[i]
      path = [arr[i]]

      for j in range(i + 1, len(arr)):
        mpy *= arr[j]
        path.append(arr[j])
        if mpy < target:
          result.append(path[:])

Show 1 reply

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:

Reading Progress

Vote for new content