Product of Array Except Self

NikhithaNikhitha
3 min read

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

MetricValue
TimeO(n)
SpaceO(1) extra ⚠️
(Output array not counted as extra space)

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

Happy Coding!

0
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