Product of Array Except Self

Problem Description

Given an integer array nums, return an array answer such that answer[i] is the product of all elements except nums[i].

You must run in O(n) time and cannot use division.

Examples

Constraints

• 2 ≤ nums.length ≤ 10⁵
• -30 ≤ nums[i] ≤ 30
• The product of any prefix or suffix fits in a 32-bit integer.

The No-Division Constraint Eliminates the Obvious Answer

The division-based shortcut is: compute the total product, divide by nums[i] for each position. Two problems: division is banned, and it breaks entirely if any element is zero. The constraint exists to push you toward a different question: what does answer[i] actually consist of?

answer[i] is the product of everything to the left of i multiplied by everything to the right of i. You can compute both halves independently with a single left pass and a single right pass.

Solution 1: Division (to show why it fails)

Multiply all elements, divide by each for its answer. Included here only to articulate why it’s ruled out.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int total = 1;
        int zeroCount = 0;
        for (int num : nums) {
            if (num == 0) zeroCount++;
            else total *= num;
        }
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (zeroCount > 1) result[i] = 0;
            else if (zeroCount == 1) result[i] = nums[i] == 0 ? total : 0;
            else result[i] = total / nums[i];
        }
        return result;
    }
}

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        from math import prod
        total = prod(x for x in nums if x != 0)
        zero_count = nums.count(0)
        result = []
        for num in nums:
            if zero_count > 1: result.append(0)
            elif zero_count == 1: result.append(total if num == 0 else 0)
            else: result.append(total // num)
        return result

#include <vector>

class Solution {
public:
    std::vector<int> productExceptSelf(std::vector<int>& nums) {
        int total = 1, zeros = 0;
        for (int n : nums) { if (n == 0) zeros++; else total *= n; }
        std::vector<int> res(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            if (zeros > 1) res[i] = 0;
            else if (zeros == 1) res[i] = nums[i] == 0 ? total : 0;
            else res[i] = total / nums[i];
        }
        return res;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Two passes.
• Space Complexity: O(1) extra (besides the output array).

Where it breaks: division is explicitly banned by the problem. And even if it weren’t, integer division truncates for non-integer results. Floating point division introduces precision errors. This approach is off the table.

Solution 2: Prefix and Suffix Products (No Division)

Two passes. In the left pass, result[i] accumulates the product of all elements to the left of i. In the right pass, multiply each position by the running suffix product, updating it as you go. The output array itself serves as the prefix storage, so no extra array is needed.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // left pass: result[i] = product of nums[0..i-1]
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // right pass: multiply each position by the running suffix product
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [1] * n

        # left pass: result[i] = product of nums[0..i-1]
        prefix = 1
        for i in range(n):
            result[i] = prefix
            prefix *= nums[i]

        # right pass: multiply each position by the running suffix product
        suffix = 1
        for i in range(n - 1, -1, -1):
            result[i] *= suffix
            suffix *= nums[i]

        return result

#include <vector>

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

        // left pass: result[i] = product of nums[0..i-1]
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            result[i] = prefix;
            prefix *= nums[i];
        }

        // right pass: multiply each position by the running suffix product
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Two linear passes.
• Space Complexity: O(1) extra. The output array doesn’t count toward space complexity by convention.

Where it breaks: this doesn’t handle the “output array doesn’t count” caveat clearly in some follow-up phrasings. If the interviewer disallows using the output array as scratch space, you’d need a separate prefix array, making space O(n). Ask for clarification upfront.

Why Not Store Separate Prefix and Suffix Arrays?

It works, and it’s arguably easier to read. prefix[i] = product of nums[0..i-1], suffix[i] = product of nums[i+1..n-1], result[i] = prefix[i] * suffix[i]. Same O(n) time, but O(n) extra space instead of O(1). The reuse trick in Solution 2 is the optimization worth knowing.

Common Mistakes

• Setting result[0] = nums[0] in the left pass. The left product of the first element is 1 (nothing to its left), not nums[0]. Starting wrong poisons every subsequent value.
• Not initializing the suffix variable to 1. If you start suffix = nums[n-1], the last element gets multiplied by itself.
• Forgetting zeros. The division approach completely breaks with zeros. The prefix/suffix approach handles them naturally since 0 just multiplies into the running product normally.

Frequently Asked Questions

Why can’t you just total the product and divide? Division is explicitly banned. Even ignoring the constraint, dividing by zero (when any element is 0) crashes the approach, requiring significant special casing.

What if there are two or more zeros in the input? Every answer[i] is 0 because both sides of any position will include at least one zero. The prefix/suffix approach handles this correctly without any special logic.

What does this problem test in interviews? Whether you can decompose a problem into two independent subproblems (left products, right products) and whether you recognize the O(1) space optimization of using the output array as intermediate storage.

← All Problems