Product of Array Except Self

Medium Problem 10 of 151 Java and Python

Problem

Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].

You must solve it in O(n) time and without using division. The products fit in a 32-bit integer.

Example 1

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Why: answer[0] = 2 × 3 × 4 = 24, and so on.

Example 2

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Constraints

2 ≤ nums.length ≤ 10⁵
-30 ≤ nums[i] ≤ 30

Explanation

The product of everything except nums[i] is (product of everything to its left) × (product of everything to its right).

Both can be built in one pass each: a running product from the left, then a running product from the right, multiplied into the same output array.

Approach 1 · Naive

Multiply all the others

Time O(n²)
Space O(1) extra

For each index, multiply every other element.

For each i, start a product at 1.
Multiply in nums[j] for every j != i.
Store the product in answer[i].

Java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    product *= nums[j];
                }
            }
            answer[i] = product;
        }
        return answer;
    }
}

Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = []
        for i in range(n):
            product = 1
            for j in range(n):
                if j != i:
                    product *= nums[j]
            answer.append(product)
        return answer

Approach 2 · Optimal

Prefix and suffix products

Time O(n)
Space O(1) extra (the output does not count)

First fill answer[i] with the product of everything left of i. Then sweep from the right with a running suffix product and multiply it in.

Set answer[0] = 1; for i ≥ 1, answer[i] = answer[i - 1] * nums[i - 1].
Set suffix = 1. Going from the last index to the first: answer[i] *= suffix, then suffix *= nums[i].
Return answer.

Java

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;
    }
}

Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        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

Complexity compared

Approach	Time	Space
Naive Multiply all the others	O(n²)	O(1) extra
Optimal Prefix and suffix products	O(n)	O(1) extra (the output does not count)

Key takeaways

"Everything except i" often splits into "everything left of i" and "everything right of i".
Dividing the total product by nums[i] breaks as soon as the array contains a zero, which is why the problem forbids it.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem