Iteration

Product Excluding Self

Given an array of numbers arr, return a new array where each entry is the product of all the entries, excluding the current entry.

You cannot use the division operator. The array will always at least 2 elements in it.

Example:

\notag \large \texttt{arr = [4,3,2,1]}\\[4bp] \large \texttt{arr = [6,8,12,24]}

Explanation: Here's the product of each element, excluding itself:

First Few Test Cases:

You can compute everything to the left of the X efficiently if you walk left-to-right:

And you can compute everything to the right of the X efficiently if you walk right-to-left:

When you're done, you can just multiply the results entry-wise to get the answer:

To simplify the code, we can make it so the empty entries are just treated like 1. This way, the algorithm is to compute [1, 4, 12, 24] and [6, 2, 1, 1] and then multiply them entry-wise.

Time Complexity $O(n)$ . We do two passes and then a final pass to multiply each entry.

Space Complexity $O(n)$ for prodLR and prodRL.

You can optimize this by getting rid of the extra arrays prodLR and prodRL so that you only need memory for the output array. This lowers the memory by a factor of 3. But it doesn't change the time or space complexity so it's not crucial.

Mark as Completed:

Submits:

productExcludingSelf

Test your code to get an output here!

productExcludingSelf(

)

Test your code to get an output here!