This question is part of NeetCode150 series.
Problem Description
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.
leetcode
Solution
APPROACH 1
Since we are not supposed to use division, one way to solve this problem is by doing some pre-processing the product of elements on the left side and right side for each index. (Prefix/Suffix Array Approach). Finally, we simply multiply the ith element in these two array to get the required value.
Example:
Array:
1 2 3 4Prefix Product:
1 1 2 6Suffix Production:
24 12 4 1Answer:
24 12 8 6
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
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] lpf = new int[n];
lpf[0] = 1;
for(int i=1; i<n; i++){
lpf[i] = nums[i-1] * lpf[i-1];
}
int[] rpf = new int[n];
rpf[n-1] = 1;
for(int i=n-2; i>=0; i--){
rpf[i] = rpf[i+1] * nums[i+1];
}
int[] ans = new int[n];
for(int i=0; i<n; i++){
ans[i] = lpf[i] * rpf[i];
}
return ans;
}
}
APPROACH 2
It’s based on the previous approach, but instead we can calculate the ans on the fly without using any extra space.
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
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
//Create left prefix product in the ans array itself
ans[0] = 1;
for(int i=1; i<n; i++){
ans[i] = ans[i-1] * nums[i-1];
}
//To save space, we will maintain product from right using this variable
int r_current = 1;
for(int i=n-2; i>=0; i--){
r_current = r_current * nums[i+1];
ans[i] = ans[i] * r_current;
}
return ans;
}
}