Product of Array Except Self
Given an integer array numsansweranswer[i]nums
The product of any prefix or suffix of nums
You must write an algorithm that runs in O(n)
Example 1
Output: [24,12,8,6]
Example 2
Output: [0,0,9,0,0]
Follow up:
Can you solve the problem inO(1)Contents
Solution 1 - using prefix and postfix arrays
In this approach, what we are going to do is, build two separate arrays prefixpostfixprefixpostfix
Once we have prefixpostfixiprefix[i-1]postfix[i+1]i01ans[i] = (i==0 ? 1 : prefix[i-1]) * (i==nums.length-1 ? 1 : postfix[i+1]);
Consider an example, nums = [1, 2, 3, 4]
-
We will create
and fill it with prefix product values:prefixJavafor(int i=0; i<nums.length; i++) { prefix[i] = nums[i] * (i ==0 ? 1 : prefix[i-1]); } array will look like thisprefix[1, 2, 6, 24] -
We will create
and fill it with postfix product values:postfixJavafor(int i=nums.length -1; i>=0; i--) { postfix[i] = nums[i] * (i==nums.length-1 ? 1 : postfix[i+1]); } array will look like thispostfix[24, 24, 12, 4] -
Once we have the
andprefix arrays, then if we want to compute product of entire array except self, then we should take the product of all values from left side of array before current element, which we can find it frompostfix array atprefix index and product of all values from right side of array after current element, which we can find it fromi-1th array atpostfix index.i+1thJavaint[] ans = new int[nums.length]; for(int i=0 ;i< nums.length; i++) { ans[i] = (i==0 ? 1 : prefix[i-1]) * (i == nums.length-1 ? 1 : postfix[i+1]); }ans array index prefix postfix ans 0 1 24 1 (because i== 0) * 24 = 241 2 24 1 * 12 = 12 2 6 12 2 * 4 = 8 3 24 4 6 * 1 (because i== nums.length -1) = 6
public class ProductOfArrayExceptSelf {
/**
* Using prefix and postfix arrays
*/
static int[] usingPrefixAndPostfixArrays(int[] nums) {
int[] prefix = new int[nums.length];
int[] postfix = new int[nums.length];
for(int i=0; i<nums.length; i++) {
prefix[i] = nums[i] * (i ==0 ? 1 : prefix[i-1]);
}
for(int i=nums.length -1; i>=0; i--) {
postfix[i] = nums[i] * (i==nums.length-1 ? 1 : postfix[i+1]);
}
int[] ans = new int[nums.length];
for(int i=0 ;i< nums.length; i++) {
ans[i] = (i==0 ? 1 : prefix[i-1]) * (i == nums.length-1 ? 1 : postfix[i+1]);
}
return ans;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where nnums
Space complexity: O(n) for the prefixpostfix
Solution 2 - using prefix and postfix arrays approach without really creating them (Answer to the follow-up question)
In this approach, we are going to use the same solution as we saw in previous approach, but without really creating prefixpostfix
We are going to create the ans
-
One thing that we do differently in this case is, instead of storing the prefix product values, we compute prefix product and store that at the next index. This is because we will be using product until index
ati th index from prefix product.i+1For example say if the input array has elements like this
when we compute prefix product at[0......k, k+1,......n] , that will be used at index0 and similarly the prefix product until1 will be used atk .k+1For example, if the input array is
, then we will fill thenums = [1, 2, 3, 4] like this:ansans array prefix index nums ans 0 1 1 (we will place 1 here, as it has no impact on product) 1 2 nums[i-1] * ans[i-1] = 1 * 1 = 1 2 3 2 * 1 = 2 3 4 3 * 2 = 6 If you notice
array after prefix values calculated and placed at thr right indexes, last element in theans array will be the right value for that index (product of all except self).ans -
In the next step, we will start from right to left from index
to indexnums.length-2 and compute the postfix and multiply that with current element in0 array.ansans array after postfix index nums ans (before prefix) ans (after prefix) 0 1 1 postfix = 12 * (nums[i+1]) = 12 * 2 = 24
ans[i] * postfix = 1 * 24 = 241 2 1 postfix = 4 * (nums[i+1]) = 4 * 3 = 12
ans[i] * postfix = 1 * 12 = 122 3 2 postfix = 4 (nums[i+1])
ans[i] * postfix = 2 * 4 = 83 4 6 6 (we dont touch it, as it is already computed correctly in prefix array)
public class ProductOfArrayExceptSelf {
/**
*
* we are going to use answer array itself to store prefix array values,
* then multiply those with postfix product
*/
static int[] usingPrefixAndPostfixProductMemoryOptimized(int[] nums) {
int[] ans = new int[nums.length];
// building prefix product values and placing them at i+1,
// as this is where we would need i.....k product at k+1 (th) index
ans[0] = 1;
for(int i=1; i<nums.length; i++) {
ans[i] = nums[i-1] *ans[i-1];
}
// compute post fix and multiply that with ans[i]
int postfix = 1;
for(int i=nums.length -2; i>=0; i--){
postfix = postfix * nums[i+1];
ans[i] = ans[i] * postfix;
}
return ans;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where nnums
Space complexity: O(1) if we dont consider ans
Above implementations source code can be found at