238. Product of Array Except Self (Medium)

https://leetcode.com/problems/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).

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

Solutions

``````class Solution {

// Calculate the left production from head to specific element.
// Calculate the right production from tail to specific element.

public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}

int len = nums.length;
int[] ans = new int[len];
ans[0] = 1;

for (int i = 1; i < len; i++) {

// Update ans[i] to assign the production of values before i to it.
ans[i] = ans[i - 1] * nums[i - 1];
}

// ans[len-1] has already sorted out.

// right production after i
int rp = 1;

for (int i = len - 2; i >= 0; i--) {
// right production after i
rp = rp * nums[i + 1];

// Since ans[i] already contains the production of values before i, we are
// expected to multiply the production of right side elements so that we can
// gain the desired production.
ans[i] = ans[i] * rp;
}

return ans;
}
}
``````

2.

``````class Solution {

// Problem requires solution without division, but this is also a good solution.

// Take care of situations that elements contain zeros

public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}

int len = nums.length;

int[] ans = new int[len];
Arrays.fill(ans, 0);

int fullProd = 1;
int zeroNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
zeroNum++;
continue;
}

fullProd *= nums[i];
}

// 1. >= 2 zeros, all the production should be 0

if (zeroNum >= 2) {
return ans;
}

// 2. 1 zero, all the production should be 0 except ith element which is of 0 value

if (zeroNum == 1) {
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
continue;
}

ans[i] = fullProd;

return ans;
}
}

// 3. 0 zero, normal situation

for (int i = 0; i < nums.length; i++) {
ans[i] = fullProd / nums[i];
}

return ans;
}
}
``````