Python O(n) solution with explanation


  • 0
    Z
    class Solution:
        def productExceptSelf(self, nums):
            if len(nums) < 2: return nums
    
            ret = [0 for i in xrange(len(nums))]
        
            '''
            From left to right, construct left-prodcut
            array, i.e., ret[i] = product(nums[0]...nums[i])
            '''
            ret[0] = nums[0]
            for i in xrange(1,len(nums)-1):
                ret[i] = nums[i] * ret[i-1]
            
            # The right product beyond current index
            rt = 1
        
            '''
            From right to left, ret[i] = ret[i-1] * rt
            '''
            for i in xrange(len(nums) - 1, 0, -1):
                ret[i] = ret[i-1] * rt
                rt *= nums[i]
            ret[0] = rt   
              
            return ret

  • 2

    You could do the first part like this:

        ret = nums[:]
        for i in xrange(1,len(nums)-1):
            ret[i] *= ret[i-1]
    

    Or at least

        ret = [0] * len(nums)
    

    instead of

        ret = [0 for i in xrange(len(nums))]
    

  • 0
    Z

    pythonic python !


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.