DEV Community

Bernice Waweru
Bernice Waweru

Posted on

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)