chevron-up bell reply instagram twitter2 feed3 finder search-25px-p0

Leetcode 238 Product of Array Except Self

2017-03-18

Question:
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to
the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].

When getting this question, the first thing comes to my mind is to use the reduce function, which can help you get the product of a number of numbers. So the code would be:

class Solution(object):
    # Solution 1
    # not passing the performance requirements
    def productExceptSelf1(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        aryRes = []
        import copy
        for e in nums:
            tmpNums= copy.deepcopy(nuts) # line 12
            tmpNums.remove(e)
            Res.append(reduce(lambda x,y:x*y, tmpNums))
        return aryRes

From the code you can see, line 12 I copy the original list to a new list, by doing this I can remove the corresponding element one by one and use the reduce function to get the product of rest numbers. For example, with given an array [1,2,3,4], you can get the product of [2,3,4] by using:

reduce(lambda x,y:x*y, [2,3,4])

However the submission did not pass the performance test, the running time: Total time: 0.000423 s (avg). So let.s move on on this journey ­čÖé

So commonly, if we want to boost our program, we can use some variables to store intermedia data. for example, if we have nums [a1, a2, a3, a4]. for each pass, we can calculate the product of all left numbers as well as the products from all right numbers. So the version 2 solution can be:

def productExceptSelf2(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    aryRes = []
    for index in range(len(nums)):
        #print nums[:index], nums[index+1:]
        product_left = reduce(lambda x,y:x*y,nums[:index]) if(nums[:index]!=[]) else 1
        product_right = reduce(lambda x,y:x*y,nums[index+1:]) if(nums[index+1:]!=[]) else 1
        aryRes.append(product_left*product_right)

    return aryRes

This time, it is a little bit faster. After using the kernprof (which is an python performance profiling tool, https://github.com/rkern/line_profiler) , the cost time is roughly Total time: 0.000114 s (avg). So we may assume that most of the time is wasted on the reduce function. After checking online, there should be a much more efficient way of replacing reduce. Based on the solution 2, we know that we can use an intermediate variables to store intermediate results. With given nums=[a1, a2, a3, a4], and we want res= [a2a3a4, a1a3a4, a1a2a4, a2a3a4], we can think about using two arrays to multiple with each other.

[1, a1, a1a2, a1a2a3]
[a2a3a4, a3
a4, a4, 1]

Aim to get:

[a2a3a4, a1a3a4, a1a2a4, a2a3a4]

So the first thing we can do is creating those two lists, and multiply them with position corresponding with each other.

def productExceptSelf3(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    size = len(nums)
    ary_left = [1] * size
    ary_right = [1] * size
    ary_res = []`

    for i in range(size-1):
        ary_left[i+1]*= ary_left[i]*nums[i]

    for i in range(size-1, 0, -1):
        ary_right[i-1]*= ary_right[i]*nums[i]

    for i in range(size):
        ary_res.append(ary_left[i]*ary_right[i])
    return ary_res

Total time: 3.3e-05 s.

Thanks for your time.

arkilis

Make Your Comments