DSA

Product of Array Except Self

Covers: Brute Force, prefix Sum, Prefix Sum - Space Optimizat…. Optimal — Time O(n), Space O(1).

August 8, 2026
PatternPrefix & Suffix ProductsOptimalO(n) time · O(1) space
Solve on LeetCode
Key insighttry it first, then reveal

We reuse the output array itself to eliminate the two auxiliary arrays.

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#

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
cpp
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(n2) --> 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
cpp
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.

cpp

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#

ApproachDescriptionTime ComplexitySpace ComplexityCode Insight
Brute ForceFor each index, multiply all elements except currentO(n²)O(1)Two nested loops → TLE on large inputs
Better (Prefix & Suffix)Precompute prefix & suffix products and multiply them for each indexO(n)O(n)Uses two extra arrays: pre[i] = product of nums[0..i-1], suff[i] = product of nums[i+1..n-1]
Optimal (Space Optimized)Use output array to store prefix product, and suffix product via one backward passO(n)O(1) (excluding output)First pass → prefix in result; second pass → multiply with suffix using a variable