Product of Array Except Self

Array Math

Problem

Given an array nums of n integers where n > 1, return an array outputsuch 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]

Thought Process

• Notice how for the specific index, what will be computed is the product of everything to the left of the element multiplied by the product of everything to the right of it.

• For getting the products of every number to the left of nums[i], we will utilize an output array of the same size. In this new array, call it "leftProduct", index i will represent the product of every nuber to the left of this index (not including it). For index 0, this will initially be 1 since no number is to the left of it. Now, for every index i, the total product of every number to the left of it multiplied together will be:

• Since our product array is storing every element to the left of index i multiplied together, to compute the current index we can just take the previous number in the original array (nums[i - 1]) and multiply it by the already computed product of every number to the left of it $(l[i -1])$. The final result will give us an array of numbers who represent all the product of numbers to the left of an index i.

• Utilizing this leftProduct array, we can use a variable to represent numbers to the right of index i, and multiply this right number variable by each element in our leftProduct array.

• To compute the new right variable, we will multiply the current num[i] in the original array by the current right variable that already represnts all the numbers to the right of index i multiplied together.

Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1 for i in range(n)]
        for i in range(1,n):
            left[i] = left[i-1]*nums[i-1]
            
        right = 1 #right product variable initially 1
        for i in range(n-1,-1,-1):
            left[i] *= right
            right = right * nums[i]
        return left
            
        

Key Facts

• Utlizing a leftProduct array for computing every number to the left of index i.

  • We just multiply the previous element in our leftProduct array (the element here already represents the product of every number to the left of the previous number in the original array) by the previous element in the original array to compute the product of every number to the left of index i.

• Utilizing a rightProduct variable, representing product of all elements to the right of index i, and multiplying this with the element at index i in our leftProduct array.

Time Complexity

• Time: $O(n)$

• Space: $O(1)$