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 !!!
Top comments (0)