Problem
Given an array, return an array where each element is the product of all other elements. Solve in O(n) without division.
Example
Input: [1,2,3,4]
Output: [24,12,8,6]Solution
Two passes: left-to-right multiplies prefix products, right-to-left multiplies suffix products.
def product_except_self(nums):
n = len(nums)
result = [1] * n
left = 1
for i in range(n):
result[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
result[i] *= right
right *= nums[i]
return resultfunction productExceptSelf(nums) {
const result = new Array(nums.length).fill(1);
let left = 1;
for (let i = 0; i < nums.length; i++) {
result[i] = left;
left *= nums[i];
}
let right = 1;
for (let i = nums.length - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, 1);
int left = 1;
for (int i = 0; i < n; i++) { result[i] = left; left *= nums[i]; }
int right = 1;
for (int i = n - 1; i >= 0; i--) { result[i] *= right; right *= nums[i]; }
return result;
}public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 1;
for (int i = 0; i < n; i++) { result[i] = left; left *= nums[i]; }
int right = 1;
for (int i = n - 1; i >= 0; i--) { result[i] *= right; right *= nums[i]; }
return result;
}Complexity
- Time: O(n)
- Space: O(1) extra
Explanation
Each element’s answer is (product of elements to its left) * (product of elements to its right). Two passes accumulate each side.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?