Product of Array Except Self

Problem Statement
Given an integer array nums
, return an array answer
such that:
answer[i] = product of all elements in nums except nums[i]
π Intuition
If we could use division, a simple approach would be:
Calculate the product of all elements.
Divide by
nums[i]
to getanswer[i]
.
But weβre not allowed to use division.
So how do we get the product of all elements except nums[i]
efficiently?
β‘οΈ Think in terms of:
Elements to the left of
i
β Prefix productElements to the right of
i
β Suffix product
Then:
answer[i] = prefix_product[i] * suffix_product[i];
π‘ Approach
We use two passes:
πΉ First Pass: Left to Right (Prefix Product)
Traverse the array and keep a running
prefixProduct
.For each index
i
, setanswer[i] = prefixProduct
, then updateprefixProduct *= nums[i]
.This gives product of all elements before
i
.
πΉ Second Pass: Right to Left (Suffix Product)
Similarly, keep a running
suffixProduct
.For each index
i
from right to left, multiplyanswer[i] *= suffixProduct
, then updatesuffixProduct *= nums[i]
.This adds product of all elements after
i
.
Final answer[i] = product of all elements except nums[i]
.
π Dry Run
Letβs say nums = [1, 2, 3, 4]
Step 1: Prefix pass
prefix = 1
answer[0] = 1 β prefix = 1 * 1 = 1
answer[1] = 1 β prefix = 1 * 2 = 2
answer[2] = 2 β prefix = 2 * 3 = 6
answer[3] = 6 β prefix = 6 * 4 = 24
Now answer = [1, 1, 2, 6]
Step 2: Suffix pass
suffix = 1
answer[3] *= 1 β 6 β suffix = 1 * 4 = 4
answer[2] *= 4 β 8 β suffix = 4 * 3 = 12
answer[1] *= 12 β 12 β suffix = 12 * 2 = 24
answer[0] *= 24 β 24
β
Final answer = [24, 12, 8, 6]
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> answer(n, 1); // Step 1: Initialize answer array with 1s
// Step 2: Prefix product pass (left to right)
int prefixProduct = 1;
for (int i = 0; i < n; ++i) {
answer[i] = prefixProduct; // Store product of all elements to the left
prefixProduct *= nums[i]; // Update prefix product
}
// Step 3: Suffix product pass (right to left)
int suffixProduct = 1;
for (int i = n - 1; i >= 0; --i) {
answer[i] *= suffixProduct; // Multiply with product of elements to the right
suffixProduct *= nums[i]; // Update suffix product
}
return answer;
}
};
π§ Time & Space Complexity
Metric | Value |
Time | O(n) |
Space | O(1) extra β οΈ |
(Output array not counted as extra space) |
problem link: https://leetcode.com/problems/product-of-array-except-self/description/
Happy Coding!
Subscribe to my newsletter
Read articles from Nikhitha directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Nikhitha
Nikhitha
π Software Developer | DSA Enthusiast | Problem Solver πΉ Sharing daily DSA solutions, coding insights, and interview prep πΉ Passionate about writing optimized & bug-free code