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 !!!