Product of Array Except Self

Instructions

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].

Attempt here

Example

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

Approach

The first idea you are likely to come up with is to find the product of all the elements in the array and divide the product by nums[i] to get the product at a given i.
However, the questions requires that we do not use the division operator.

Another approach would be to maintain a prefix that stores the product of elements before array[i] and a postfix that stores the product of elements occuring after array[i].

Implementation

def productExceptSelf(self, nums: List[int]) -> List[int]: result = [1] * (len(nums)) prefix = 1 postfix = 1 for i in range(len(nums)): result[i] = prefix prefix *= nums[i] for i in range(len(nums) - 1, -1, -1): result[i] *= postfix postfix *= nums[i] return result 

When calculating the postfix we iterate through the array with -1 step. A negative step value in a range() function generates the sequence of numbers in reverse order.

This solution uses O(1) space complexity and O(n) time complexity.

Video Solution
Happy learning !!!