Python solution with detailed explanation


  • 0
    G

    Solution

    Product of Array Except Self https://leetcode.com/problems/product-of-array-except-self/

    Solution using two arrays

    • First engineer a solution using two arrays.
    class Solution(object):
        def productExceptSelf(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            N = len(nums)
            output1 = [1]*N
            for i in xrange(1,N):
                output1[i] = output1[i-1]*nums[i-1]
            output2 = [1]*N
            for i in xrange(N-2, -1, -1):
                output2[i] = output2[i+1]*nums[i+1]
            for i in xrange(N):
                output1[i] = output1[i]*output2[i]
            return output1
    

    Optimizing two array solution

    • Merge the last two for loops.
    for i in xrange(N-2, -1, -1):
    		output2[i] = output2[i+1]*nums[i+1]
    for i in xrange(N):
    		output1[i] = output1[i]*output2[i]
    
    for i in xrange(N-2, -1, -1):
    		output2[i] = output2[i+1]*nums[i+1]
    		output1[i] = output1[i]*output2[i]
    
    • Now we can remove output2 array and replace with the prev value
            prev = 1
            for i in range(N-2, -1, -1):
                prev *= nums[i+1]
                output1[i] *= prev
    

    Optimized Code

    class Solution1(object):
        def productExceptSelf(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            N = len(nums)
            output1 = [1]
            for i in range(1,N):
                output1.append(output1[-1]*nums[i-1])
            prev = 1
            for i in range(N-2, -1, -1):
                prev *= nums[i+1]
                output1[i] *= prev
            return output1
    

Log in to reply
 

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