Product of Array Except Self
Given an integer array numsansweranswer[i]nums[i]
Example 1
Output: [24, 12, 8, 6]
Example 2
Output: [0, 0, 9, 0, 0]
How to Think About It
Step 1: Why not divide?
Multiplying everything and dividing by nums[i]
Step 2: Split "everything except i" into two parts
Everything except nums[i]
answer[i] = (product of nums[0..i-1]) × (product of nums[i+1..n-1])
Step 3: Left products, left to right
The product of everything left of ii - 1nums[i - 1]answer
Step 4: Right products, right to left, in a single variable
Walk back from the end, keeping rightianswer[i]nums[i]right
Walkthrough
nums = [1, 2, 3, 4]
| i | Left product | Right product | answer[i] |
|---|---|---|---|
| 0 | 1 | 2 × 3 × 4 = 24 | 24 |
| 1 | 1 | 3 × 4 = 12 | 12 |
| 2 | 1 × 2 = 2 | 4 | 8 |
| 3 | 1 × 2 × 3 = 6 | 1 | 6 |
Java Solution
The first loop stores left products in answer
import java.util.Arrays;
public class ProductOfArrayExceptSelf {
public static int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
answer[0] = 1;
for (int i = 1; i < n; i++) {
answer[i] = answer[i - 1] * nums[i - 1]; // product of everything left of i
}
int right = 1; // product of everything right of i
for (int i = n - 1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(productExceptSelf(new int[] {1, 2, 3, 4})));
// [24, 12, 8, 6]
System.out.println(Arrays.toString(productExceptSelf(new int[] {-1, 1, 0, -3, 3})));
// [0, 0, 9, 0, 0]
}
}
The original implementation,
Complexity
- Time: O(n): two passes.
- Space: O(1) besides the output.
The same "everything to the left, everything to the right" split appears with sums in