Product of Array Except Self
For each position, calculate the product of all array values except the value at that position. Use linear time and do not use division.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1. At least two values; all products fit in a signed 64-bit integer.Expected result
The products separated by spaces.Case 1
Input
2 3 4
Expected output
12 8 6
Case 2
Input
0 5 2
Expected output
10 0 0
Case 3
Input
0 2 0
Expected output
0 0 0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The product except nums[i] is the left product times the right product. Two extra arrays for prefixes and suffixes use more than constant space. Write prefix products into the answer left to right, then multiply a running suffix from the right, using only the output array.
We define two variables left and right to represent the product of all elements to the left and right of the current element, respectively. Initially, left = 1 and right = 1. We define an answer array ans of length n.
First, we traverse the array from left to right. For the i-th element, we update ans[i] with left, then multiply left by nums[i].
Next, we traverse the array from right to left. For the i-th element, we update ans[i] to ans[i] × right, then multiply right by nums[i].
After the traversal, we return the answer array ans.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (int i = n - 1, right = 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.