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:
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
Comments