It's the Xinrui Ma

Blog

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

Example:

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

Solution:
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]