Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Nabeel Keblawi
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 Gurus
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))