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

0% completed

Vote For New Content
softest mike
Two for loops O(N^2) solution

softest mike

Nov 27, 2024

class Solution:   def findSubarrays(self, arr, target):     result = []     n = len(arr)     for i in range(n):       subarray_starting_at_i = []       curr_subarr_i = []       if arr[i] < target:         curr_subarr_i.append(arr[i])         subarray_starting_at_i.append(curr_subarr_i.copy())         product = arr[i]         for j in range(i+1, n):           product = product * arr[j]           if product < target:             curr_subarr_i.append(arr[j])             subarray_starting_at_i.append(curr_subarr_i.copy())           else:             break         result.extend(subarray_starting_at_i)       else:         continue     return result

0

0

Comments
Comments
softest mike
softest mikea year ago

In the worst case, there will be n-i runs at each iterator position. That gives 1+2+3+...+N. The sum of the series will result in O(N^2)