Given an integer array
nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. You must solve it in O(n) time and without using the division operator.Example
nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Each position holds the product of all other elements: result[0] = 2 * 3 * 4 = 24, result[1] = 1 * 3 * 4 = 12, result[2] = 1 * 2 * 4 = 8, result[3] = 1 * 2 * 3 = 6.
Make two passes over the array. First pass goes left-to-right, building up a running product of everything to the left of each index. Second pass goes right-to-left, multiplying in the running product of everything to the right. Each position ends up with the product of all elements except itself — no division needed.
Why this works
The product of all elements except index i equals (product of everything left of i) times (product of everything right of i). You can compute both with two simple passes, avoiding division entirely. The first pass builds left-products, and the second pass multiplies in right-products.
Step by step
- Left-to-right pass — for each position, store the running product of all elements before it.
- Right-to-left pass — walk backwards, multiplying each position by the running product of all elements after it.
- Result is complete — each position now holds the product of every element except itself.
Time: O(n)
Space: O(1)
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int prefix = 1;
for (int i = 0; i < n; i++) {
result[i] = prefix; // product of everything to the left
prefix *= nums[i];
}
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= suffix; // multiply in product of everything to the right
suffix *= nums[i];
}
return result;
}
}
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, 1);
int prefix = 1;
for (int i = 0; i < n; i++) {
result[i] = prefix; // product of everything to the left
prefix *= nums[i];
}
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= suffix; // multiply in product of everything to the right
suffix *= nums[i];
}
return result;
}
};
def productExceptSelf(nums: list[int]) -> list[int]:
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix # product of everything to the left
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix # multiply in product of everything to the right
suffix *= nums[i]
return result