Topic: Arrays & Hashing
Soln 1 (prefix & suffix):
Get the length of the input list and create 2 lists (prefix and suffix) and assign 1 to them
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.
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.
return a combined multiplication of both list.
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)
Create an array result of the same length as nums, with all elements set to 1.
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].
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].
Return the result array.
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.
total_product = reduce(lambda x, y: x * y, nums)
result = [total_product // num for num in nums]
return result
Notes: None
