[Java] Product of all elements in array excluding each position

Given an array of integers, return another array which contains in each position the result of the multiplication of all elements in the array, excluding the element in that position.

Example: [1, 2, 3] results in [6, 3, 2]

We have two variants, one allows zeros and the other doesn't. Additionally we have an optional challenge to try and solve it without using division.

We can see the O(N^2) solution with two indices works find and uses O(1) space.

However there must be some mathematical property or observation that we can use to reduce that time to O(N).

Variant 1: no zeros allowed and use division

We can notice that to get the answer for each position we need to multiply ALL elements in the array, then for each position divide this total for the element itself to exclude it. If no element is 0, we can do this in two passes.

Variant 2: zeros allowed and avoid division

Another thing we can notice is that for each position, the result is the multiplication of ALL elements on the LEFT and RIGHT of that particular position.

We can therefore use extra O(N) space and create two new arrays, leftToRight and rightToLeft which we fill scanning the input in the two directions and setting for each position the result of the multiplication of the element in the PREVIOUS (left to right) or NEXT (right to left) position in the input for the element in the PREVIOUS (left to right) or NEXT (right to left) position in the corresponding temporary array.

Since the first element in both cases has no predecessor or successor, we set it to 1 and start our loops from the next element.

Now we just need to combine these partial results by multiplying them together at each position.

You can find my implementation of prodAllExcludingElementAtINotAllowZero and prodAllExcludingElementAtIAllowZero on my Gist along with some tests in ProdAllExcludingElementAtIJTests.