What's the time complexity of prod() in math in Python

user_14102808 0
Viewed 866

Summary)

  1. What's the time complexity of math.prod()
  2. How to improve this code to get to the pass

Details)

Currently working on 'Product of Array Except Self' on Leetcode

My first code was:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        product_list = []

        for index in range(len(nums)):
            deleted_value = nums.pop(index)
            product_list.append(math.prod(nums))
            nums.insert(index, deleted_value)
            
        return product_list

and thought it was 'delete and insert' in a dynamic array causing problems with the time limit.

So, I corrected some lines to:

class Solution:
    def product_except_self(self, nums):
        product_list = []

        for index in range(len(nums)):
            temp = nums[index]
            nums[index] = 1
            product_list.append(math.prod(nums))
            nums[index] = temp

        return product_list

As far as I'm concerned, ' = ' and append operation has the time complexity of O(1), so thinking that math.prod is the one posing problems here, except 'for' which is O(n).

Please enlighten me about the time complexity here and some tips to get a pass on this question.

product math time-complexity python-3.x python
2 Answers

  1. It's almost definitely O(n); Appending is O(1), but amortized over many calls. It depends on the implementation but a few of the calls are going to have to reallocate larger memory and copy everything that exists so far into the new space.

  2. The point of these challenges is to get you to think of the better approach you could take, and practice learning to recognize how you think about the usual approach and the paths that take you to the better one so that you will be able to do that kind of thinking more easily on a non-trivial problem. That said: You could calculate the full array product once only, then divide that product by each array element to produce the results. Use a generator or list comprehension.

dlamblin_4590

First calculate the prefix product of all the elements before the current element. then Calculate the product of all the elements after the element. Finally zip and multiply them.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        i,p,s,t=1,1,1,1
        m,k=[1],[1]
        n=nums[::-1]
        while i<len(nums):
            p=p*nums[i-1]
            m.append(p)
            i+=1
        while s<len(n):
            t=t*n[s-1]
            k.append(t)
            s+=1
        return [x*y for x,y in zip(m,k[::-1])]
user_130861280
Related