Product of Array Except Self — Editorial

Opening the reading…

Intuitioneach position is the product of two independent sides

For index i, every element that belongs in answer[i] is either to the left of i or to the right of i. The element at i itself must be excluded, so the desired value is the product of nums[0] through nums[i - 1], multiplied by the product of nums[i + 1] through nums[n - 1]. No division is needed when those two products are built directly.

Use the output array to remember the product on the left. At index i, store the product of all elements before i, not including nums[i]. Then scan from right to left with a running suffix product. Multiplying the stored prefix by the current suffix completes answer[i]. The empty side of the array contributes 1, which is why the first prefix and the initial suffix both start at 1.

Approachtwo directional passes, one reused array

Create ans with n entries and set ans[0] to 1, because index 0 has no elements on its left and an empty product must not change multiplication.

Scan from left to right starting at index 1, setting ans[i] to ans[i - 1] * nums[i - 1]. This records exactly the product before i; using nums[i] here would incorrectly include the excluded element.

Set suffix to 1 and scan from right to left. Before incorporating nums[i], suffix is the product of every element strictly to the right of i.

Multiply ans[i] by suffix, combining the stored left product with the right product to form the complete product except nums[i].

Update suffix with suffix *= nums[i] after writing ans[i], so the current element becomes available as a right-side value for the next index to the left.

Return ans after both passes. Zeros need no special branch: a zero naturally makes the relevant prefix or suffix product zero, while an index containing the only zero receives the product of the nonzero sides.

Complexitythe output array doubles as working storage

MEASURE	BOUND	WHY
Time	O(n)	The first pass visits each index once and the second pass visits each index once. Each iteration performs constant work, so the total number of operations is 2n plus setup and return work, which is O(n).
Space	O(1) extra	ans is required output and is excluded from the working-space bound. Apart from it, the algorithm stores only n and suffix, so the extra space is constant for every input shape; there is no recursive stack or auxiliary array.

Here n is the length of nums.

Annotated solutionC++ · two passes · output reused for prefix products

CPPStore left products in ans, then multiply each one by a right product carried from the end.

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        ans[0] = 1;

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

        int suffix = 1;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }

        return ans;
    }
};

The order inside the right-to-left loop is the central detail. At the start of iteration i, suffix excludes nums[i], so it is exactly the product that answer[i] needs from the right. Updating suffix only afterward preserves that meaning. The same ordering also handles the last index, whose right side is empty and therefore contributes 1.

The two-array alternativeclearer bookkeeping, but not an optimisation

A competent alternative is to build a prefix array and a suffix array separately, then multiply prefix[i] by suffix[i] for every index. This makes both meanings visible and can be easier to teach or debug, but it uses O(n) extra space in addition to the required output. Reusing ans removes those arrays without changing the time bound, so the reference arrangement is the space optimisation.

CPPSeparate prefix and suffix arrays make each side explicit at the cost of linear extra space.

#include <vector>
using namespace std;

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

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

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

        for (int i = 0; i < n; ++i) {
            ans[i] = prefix[i] * suffix[i];
        }

        return ans;
    }
};