Product of Array Except Self

MediumArrays & HashingBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an integer array nums. Return an array answer of the same length where answer[i] is the product of every element of nums except nums[i]. You may not use division, and your solution must run in O(n) time. The array can contain zeros and negative numbers. As a follow-up, use only O(1) extra space, where the output array does not count as extra space.

Examples

nums = [1,2,3,4] returns [24,12,8,6]

answer[0] = 2 * 3 * 4 = 24, answer[1] = 1 * 3 * 4 = 12, answer[2] = 1 * 2 * 4 = 8 and answer[3] = 1 * 2 * 3 = 6.

nums = [-1,1,0,-3,3] returns [0,0,9,0,0]

Every product that includes the 0 at index 2 is 0. Only answer[2] leaves that 0 out, giving -1 * 1 * -3 * 3 = 9.

nums = [0,4,0] returns [0,0,0]

With two zeros, every product still includes at least one of them, so every entry is 0. Dividing a total product by nums[i] would fail here.

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of the first i or the last i elements of nums fits in a 32-bit integer, for any i.

Hints

Hint 1

The product of everything except nums[i] splits into two independent pieces: everything to the left of i and everything to the right of i.

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

answer[i] is the product of everything before i times the product of everything after i. First pass, left to right: fill answer with running prefix products, so answer[i] = nums[0] * ... * nums[i - 1] and answer[0] = 1. Second pass, right to left: keep one running suffix product, multiply it into answer[i], then fold nums[i] into it. No division is needed and zeros need no special case. O(n) time, O(1) extra space beyond the output.

Time

O(n)

Space

O(1)

Pitfall

Dividing the total product by nums[i]: division is banned, and it breaks as soon as the array contains a 0. Also keep the offsets straight: answer[i] combines the prefix ending at i - 1 and the suffix starting at i + 1, never nums[i] itself.

Solutions

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }
}

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        answer = [1] * n
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1]
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]
        return answer