Leetcode: Product of Array Except Self

Problem link

Problem description

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

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

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

We simply want to return a list result such as for each element we have the product of the elements before and the elements after,in example 1 we see

• 24 = 2*3*4
• 12 = 1*3*4
• 8 = 1*2*4
• 6 = 1*2*3

So for the solution we want to have a list that has the pre-product of elements and another post-product (this idea is by https://neetcode.io/roadmap go check this amazing website)

Solution steps

Step one

res = [1] * (len(nums))
prefix = 1
for i in range(len(nums)):
    res[i] = prefix
    prefix *= nums[i]

for this step we create a res list = [1,1,1,1], imaging the nums = [1,2,3,4]

and when we enter the for loop we begin to add the prefixes at each element position for nums, so res values would be like so:

• i = 0, res[0] = 1 (because its the first element), prefix = 1 (1*1)
• i = 1, res[1] = 1 (because the prefix of element 2 is 1),prefix = 2(1*2)
• i = 2, res[2] = 2 (because the prefix of element 3 is 2),prefix = 6(3*2)
• i = 3, res[3] = 6 (because the prefix of element 4 is 6),prefix = 24(6*4)

res = [1 ,1 ,2 ,6]

Loop ends

Step two

postfix = 1
for i in range(len(nums) - 1, -1, -1):
    res[i] *= postfix
    postfix *= nums[i]
return res

and when we enter the for loop we begin to add the postfixes at each element position for nums and multiply it with the old prefixes that we added earlier, so res values would be like so:

• i = 3, res[3] = 6 (because its the last element), postfix = 4(1*4)
• i = 2, res[2] = 8 (4(post) * 2(pre)), postfix = 12(4*3)
• i = 1, res[2] = 12 (12(post)*1(pre)),postfix = 24(12*2)
• i = 0, res[3] = 24(24(post)*1(pre)),postfix = 24

Loop ends

res = [24,12,8,6]

Omar Ayman is a Egyptian writer and data scientist currently based in Egypt where He is finishing his Masters degree. Find him on Twitter @OmarAymanOmarTa for as long as it exists.