Two Pointer: Subarrays with Product Less than a Target Python


Mon Sep 26 2022 23:46:41 GMT+0000 (UTC)

Saved by @bryantirawan #python #grokking

def find_subarrays(arr, target):
  def Remove(lst):
    return ([list(i) for i in {*[tuple(sorted(i)) for i in lst]}])
  result = []
  #iterate through arr (up to len(arr) - 1) 
  for i in range(len(arr) - 1): 
      first = arr[i]
      second = arr[i + 1] 
      product = first * second 
      if first < target and first not in result: 
      if second < target and second not in result: 
      if product < target: 
        result.append([first, second]) 

  return Remove(result)  

#alternate solution that avoids making duplicate sublists in the first place 
from collections import deque

def find_subarrays(arr, target):
  result = []
  product = 1
  left = 0
  for right in range(len(arr)):
    product *= arr[right]
    while (product >= target and left <= right):
      product /= arr[left]
      left += 1
    # since the product of all numbers from left to right is less than the target therefore,
    # all subarrays from left to right will have a product less than the target too; to avoid
    # duplicates, we will start with a subarray containing only arr[right] and then extend it
    temp_list = deque()
    for i in range(right, left-1, -1):
  return result

def main():
  print(find_subarrays([2, 5, 3, 10], 30))
  print(find_subarrays([8, 2, 6, 5], 50))


For regular solution: Time: O(N) Space: O(N) For alternate solution: Time: O(N^3) worst case Space: O(N)