Two Pointer: Subarrays with Product Less than a Target Python

PHOTO EMBED

Mon Sep 26 2022 23:46:41 GMT+0000 (Coordinated Universal Time)

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: 
          result.append([first]) 
      if second < target and second not in result: 
          result.append([second])
      if product < target: 
        result.append([first, second]) 
      else: 
          continue 
    

  
  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):
      temp_list.appendleft(arr[i])
      result.append(list(temp_list))
  return result


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


main()
content_copyCOPY

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

https://www.educative.io/courses/grokking-the-coding-interview/RMV1GV1yPYz