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
class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] res = new int[n];
int[] prodFromLeft = new int[n];
prodFromLeft[0] = 1;
for (int i = 1; i < n; i++) {
prodFromLeft[i] = prodFromLeft[i - 1] * nums[i - 1];
}
int[] prodFromRight = new int[n];
prodFromRight[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
prodFromRight[i] = prodFromRight[i + 1] * nums[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = prodFromLeft[i] * prodFromRight[i];
}
return res;
}
}
(2) Follow up
class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, 1);
int temp = 1;
for (int i = 0; i < n; i++) {
res[i] = temp;
temp *= nums[i];
}
temp = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= temp;
temp *= nums[i];
}
return res;
}
}