This is the solution about Leetcode - Product of Array Except Self.

Description

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

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

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

Solution

Analysis

Solution1

Let’s take an example:

1
2
3
Array: 1 2 3 4 5
Left: 1 1*2 1*2*3 1*2*3*4
Right: 2*3*4*5 3*4*5 4*5 5

Given array[1, 2, 3, 4, 5], regarding the third number 3, the product of array except 3 is 1 2 and right is 4 5. The product is left * right.

So time complexity is O(n+n), the extra space is O(1).

Solution2

Similar with Solution1, instead of variable temp, we use result[0] to store right product.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution1 {
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
result[0] = 1;
for(int i=0; i<nums.length; i++) {
result[i] = result[i-1] * nums[i-1];
}
int temp = 1;
for(int i=nums.length-1; i>=0; i--) {
result[i] *= temp;
temp *= nums[i];
}
return result;
}
}
public class Solution2 {
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
result[0] = 1;
for(int i=0; i<nums.length; i++) {
result[i] = result[i-1] * nums[i-1];
}
for(int i=nums.length-1; i>=0; i--) {
result[i] *= result[0];
result[0] *= nums[i];
}
return result;
}
}