It's the Xinrui Ma


Product of Array Except Self

Posted by in LeetCode on

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].


Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

1. Since we can’t use divide, we will calculate two parts, the left product and the right product, separate by the current index i
2. We first calculate the left product , store them to res array. so res[i] means the left product for the current number i. Note: res[0] = 1 ( To future me: Figure this out yourself pls)
3. We can calculate from right side of the array, calculate the right product of the current index i , store them to a variable right;
4. res[i] = res[i] * right;
5. update right = right * nums[i]