238. Products of Array Discluding Self

Topic: Arrays & Hashing

Soln 1 (prefix & suffix):

1. Get the length of the input list and create 2 lists (prefix and suffix) and assign 1 to them

2. Iterate through the input list starting from the second element (index 1) because the first element (index 0) has no elements to its left.
   For each element, set the current position in the prefix list to the product of the previous position in the prefix list and the previous element in the original list nums.

3. Iterate through the input list in reverse order starting from the second-to-last element (index n-2) because the last element (index n-1) has no elements to its right.
   For each element, set the current position in the suffix list to the product of the next position in the suffix list and the next element in the original list nums.

4. return a combined multiplication of both list.
   

x = len(nums)
prefix = [1] * x
suffix = [1] * x

for index in range(1, x):
    prefix[index] = prefix[index - 1] * nums[index - 1]    

for index in range(x -2, -1, -1):
    suffix[index] = suffix[index+1] * nums[index + 1]   

return [prefix[i] * suffix[i] for i in range(x)]

Soln 2 (prefix & suffix)

1. Create an array result of the same length as nums, with all elements set to 1.

2. Initialize prefix to 1, Iterate over nums from left to right, For each element i, set result[i] to prefix and update prefix by multiplying it with nums[i].

3. Initialize suffix to 1, Iterate over nums from right to left, For each element i, multiply result[i] by suffix and update suffix by multiplying it with nums[i].

4. Return the result array.
   

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1] * len(nums)
        pre = 1

        for i in range(len(nums)):
            result[i] = pre
            pre *= nums[i]
        suf = 1
        for i in range(len(nums) -1, -1, -1):
            result[i] *=suf
            suf *= nums[i]  

        return result

Soln 3:

There is a lazy solution where all you have to do is multiply all the elements in the list to get the total product, e.g using reduce (imported from functool) then divide by the element and return a list of the solution.
The drawback of this is it uses division and it fails when any element in the list is zero.

def productExceptSelf(self, nums: List[int]) -> List[int]:
        total_product = reduce(lambda x, y: x * y, nums)

        result = [total_product // num for num in nums]

        return result

Notes: None