educative.io

Educative

Why is it necessary to have left pointer follow right pointer?

Couldn’t it be simpler to just use a nested list with an ongoing product? It would make the solution much simpler. I’m just worrying I’m missing something and that my solution’s complexity is greater than O(N^3). What do you think?

def find_subarrays(arr, target):
  res = []
  for i, a in enumerate(arr):  # O(N)
    p, subarr = 1, []
    for b in arr[i:]:  # O(N)
      p *= b
      if p >= target:
        break
      
      subarr.append(b)
      res.append(subarr.copy())  # copy costs O(N)
      
  return res  # --> O(N^3)
1 Like