Leetcode 238 product of array except self

Leetcode solution of problem 238 : product of array except self

Brute Force solution:
-------------------------------
Use nested for loop to calculate product each time except this current element.

Better solution:
--------------------
Use two arrays left and right and calculate and store the product of the left and right side, finally multiplying the left and right array to find the result.

Efficient solution:
----------------------
As we think deeper, we can see that we won't need the right array, basically we can update the result array in the first loop the same as the left array, all the multiplication part we can do from the third loop in the second loop and get rid of the right array as well.

Solution Tricks Run time Space
Brute Force solution Calculate for all pairs using nested for loop O(n^2) constant
Improved solution Store the left and right product in extra arrays O(n) O(n)
Efficient solution Combine left and right arrays to the result array O(n) constant