Back to course home
0% completed
Vote For New Content
My solution with O(N^2) for both time and space complexity
Nabeel Keblawi
Oct 7, 2024
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
0
0
Comments
Comments
Design Gurus10 months ago
This is still an O(N^3) solution. The following line to create a list from an existing list takes an additional O(N):
result.append(list(subArray))