Problem
You are given an integer arraynums.
Return an array
answer such that answer[i] is equal to the product of every element in nums except nums[i].
The solution should run in
O(n) time and should not use division.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,2,3,4]Output
[24,12,8,6]Solution
For every position, the required product can be divided into two parts: the product of all elements to its left and the product of all elements to its right.We can first store the product of all elements to the left of each position in the result array. We then traverse the array from right to left and multiply each result by the product of all elements to its right.
This allows us to calculate the result using only the output array and one variable, without creating separate prefix and suffix arrays.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
// Store prefix products.
int prefix = 1;
for (int i = 0; i < n; i++) {
answer[i] = prefix;
prefix *= nums[i];
}
// Multiply by suffix products.
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
}
Complexity
The array is traversed twice, resulting inO(n) time complexity. The output array is used to store the prefix products, and only constant extra space is used apart from the output array, resulting in O(1) extra space.