Leetcode - Product of Array Except Self

Question

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

This is an arrays question.

Idea

• Needs to run in one pass (O(n) time)
• Brute force:
  • Nested for loop, for each element in the array, pop the current element form the array and multiply the rest of the elements, add the product to a results list
• We want to essentially do a forward pass, and a backward pass through the array since the product of array except self is essentially just the product of the elements before and after “self”
• On the forward pass:
  • We keep a “prefix” variable to store the product up to the nth element
  • We append “prefix” to our result
  • We update prefix by multiplying it by the nth element
• On the backward pass:
  • We keep a “postfix” variable to store the product up to the nth element where n is counted from the end of the array
  • We multiply res[i] by postfix
  • we update postfix by multiplying it by the nth element
• After the backwards pass, each index will be the product of the products of the elements that came before it, and after it being the product off array except self

Solution