Practice Here

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].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Brute Force Approach#

For each position i, the product of all elements except nums[i] is just the product of everything to its left multiplied by the product of everything to its right. The brute-force recomputes both sub-products from scratch for every index, leading to two inner loops per element and O(n²) total work.

• For every element (i)
  • Find product of all the elements before it
  • Find product of all elements after it
  • Club the product

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result;

        for(int i=0;i<nums.size();i++)
        {
            int p = 1;
            for(int j=0;j<i;j++)
                p *= nums[j];
            for(int j=i+1;j<nums.size();j++)
                p *= nums[j];

            result.push_back(p);
        }
        return result;
    }
};

Time Complexity: O(n²) --> TLE

Space Complexity: O(1)

Better Approach: prefix Sum#

The key observation is that result[i] = (product of all elements before i) * (product of all elements after i). By precomputing a prefix-product array and a suffix-product array in two separate linear passes, we can answer every query in O(1) and avoid all redundant work. The trade-off is O(n) extra space for the two auxiliary arrays.

• Find prefix and suffix product for all elements beforehand

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);

        vector<int> pre(n,1), suff(n,1);
        for(int i=1;i<n;i++)
            pre[i] = pre[i-1] * nums[i-1];

        for(int i=n-2;i>=0;i--)
            suff[i] = suff[i+1] * nums[i+1];

        for(int i=0;i<n;i++)
            result[i] = pre[i] * suff[i];

        return result;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Optimal Approach: Prefix Sum - Space Optimization#

We reuse the output array itself to eliminate the two auxiliary arrays. In the first forward pass, result[i] is filled with the prefix product nums[0..i-1]. In the second backward pass, a single running variable suffix accumulates the suffix product and is multiplied into result[i] in-place — so by the time the backward pass ends, result[i] holds prefix * suffix, which is exactly the product of all elements except nums[i]. This achieves O(1) extra space while preserving O(n) time.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, 1);

        for(int i=1;i<n;i++)
            result[i] = result[i-1] * nums[i-1];

        int suffix = 1;
        for(int i=n-2;i>=0;i--){
            suffix *= nums[i+1];
            result[i] *= suffix;
        }
            
        return result;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Summary#