LeetCode [238] Product of Array Except Self

238. Product of Array Except Self

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int prod = 1, n = nums.size(), tmp = 1; vector<int> output(n,1); for(int i=1; i<n; ++i) { output[i] = tmp * nums[i-1]; tmp = output[i]; } tmp = 1; for(int i=n-2; i>=0; --i) { output[i] *= (tmp*nums[i+1]); tmp *= nums[i+1]; } return output; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] output = new int[n]; for(int i=0; i<n; ++i){ if(i==0) output[i] = 1; else output[i] = output[i-1]*nums[i-1]; } int p = nums[n-1]; for(int i=n-2; i>=0; --i){ if(i==0) output[i] = p; else output[i] = output[i]*p; p *= nums[i]; } return output; } }