[LC] 238. Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Approach

This problem is a bit tricky. We can do it with division but in the note, we shouldn’t do that. So, first we need to find the pattern. Let’s say prod[i] is a product except itself (i) then:

prod[0] = nums[1] x nums[2] x nums[3]
prod[1] = nums[0] x prod[2] x nums[3]
prod[2] = nums[0] x nums[1] x nums[3]
prod[3] = nums[0] x nums[1] x nums[2]

Here, we can see some patterns that maybe there is two product (in the above example, see italics and bolds) It also similar as trapping rain water problem or buy and sell stock problem because we can solve it by comparing left and right.

In here, we can see prod[i] = nums[0]*nums[1]*…*nums[i-1]*nums[i+1]*…*nums[N] So, we can split into multiple of before/after position of “i”. To sum up:

prod[i] = products_from_left[i-1]*products_from_right[i+1] where products_from_left[i] = nums[0]*nums[1]*…*nums[i] and products_from_right[i] = nums[i]*nums[i+1]*…*nums[N]

So, we can simply calculate products_from_left and products_from_right. Let’s see my first approach:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        products_from_left, products_from_right = [1]*(n+1), [1]*(n+1) #Initialize
        
        for i in range(1,n):
            products_from_left[i] = products_from_left[i-1] * nums[i-1]
            products_from_right[n-i-1] = products_from_right[n-i] * nums[n-i]
            
        prod = [1]*n
        for i in range(n):
            prod[i] = products_from_left[i] * products_from_right[i]
            
        return prod

I just implemented all of my explanation above. It beats 12.83% of submissions. Bad but doesn’t matter. but soon I realized it can be much slower than a single loop or maybe I’m wasting spaces like products_from_right and products_from_left. Actually, the follow-up tasks solve it with constant space complexity. So, I was thinking maybe we can use the prod array only. Let’s brought previous equations for the prods:

prod[i] = nums[0]*nums[1]*…*nums[i-1]*nums[i+1]*…*nums[N]

Since multiple can be exchanged between left/right equation, we may first multiple first [0]~[i-1] parts and multiple remain [i+1]~[n] part. So, we can first calculate products_from_right saving directly into the prod, then calculate products_from_left from the right and multiple with the prod.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prod = [1]*(n+1)
        
        for i in range(1,n):
            prod[i] = prod[i-1] * nums[i-1]
            
        mul_sofar = 1
        for i in range(n,0,-1):
            prod[i-1] *= mul_sofar
            mul_sofar *= nums[i-1]
            
            
        return prod[:-1]

Time Complexity: O(N)
Space Complexity: O(1)

Submission

Runtime: 248 ms, faster than 51.06% of Python3 online submissions for Product of Array Except Self.
Memory Usage: 21.5 MB, less than 46.53% of Python3 online submissions for Product of Array Except Self.