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 get answer[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 product

• Elements 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, set answer[i] = prefixProduct, then update prefixProduct *= 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, multiply answer[i] *= suffixProduct, then update suffixProduct *= 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

problem link: https://leetcode.com/problems/product-of-array-except-self/description/

Happy Coding!