Leetcode
Dynamic Programming
238 Product of Array Except Self

1. Question

Given an array ofn_integers where_n> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].
Solve itwithout divisionand 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 arraydoes notcount as extra space for the purpose of space complexity analysis.)

2. Implementation

(1) DP
1
class Solution {
2
public int[] productExceptSelf(int[] nums) {
3
if (nums == null || nums.length == 0) {
4
return new int[0];
5
}
6
int n = nums.length;
7
int[] res = new int[n];
8
int[] prodFromLeft = new int[n];
9
10
prodFromLeft[0] = 1;
11
12
for (int i = 1; i < n; i++) {
13
prodFromLeft[i] = prodFromLeft[i - 1] * nums[i - 1];
14
}
15
16
int[] prodFromRight = new int[n];
17
prodFromRight[n - 1] = 1;
18
19
for (int i = n - 2; i >= 0; i--) {
20
prodFromRight[i] = prodFromRight[i + 1] * nums[i + 1];
21
}
22
23
for (int i = 0; i < n; i++) {
24
res[i] = prodFromLeft[i] * prodFromRight[i];
25
}
26
return res;
27
}
28
}
Copied!
(2) Follow up
1
class Solution {
2
public int[] productExceptSelf(int[] nums) {
3
if (nums == null || nums.length == 0) {
4
return new int[0];
5
}
6
int n = nums.length;
7
int[] res = new int[n];
8
Arrays.fill(res, 1);
9
int temp = 1;
10
for (int i = 0; i < n; i++) {
11
res[i] = temp;
12
temp *= nums[i];
13
}
14
15
temp = 1;
16
for (int i = n - 1; i >= 0; i--) {
17
res[i] *= temp;
18
temp *= nums[i];
19
}
20
return res;
21
}
22
}
Copied!

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)
Follow up: 时间复杂度O(n), 空间复杂度O(n)