6.Product of Array Except Self

MediumBlind 75Arrays & Hashing · 6/9

Problem

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

You must solve it in O(n) time and without using division. Every prefix and suffix product is guaranteed to fit in a 32-bit integer.

Examples

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: answer[0] = 2·3·4 = 24, answer[1] = 1·3·4 = 12, answer[2] = 1·2·4 = 8, answer[3] = 1·2·3 = 6.

Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Only the position holding the zero escapes it: (-1)·1·(-3)·3 = 9.

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix fits in a 32-bit integer.
Follow-up: use O(1) extra space (the output array does not count).

💡 Key Insight

The product of everything except nums[i] splits into two independent parts: the product of everything to its left and the product of everything to its right. Both can be computed with running products — a left-to-right prefix pass and a right-to-left suffix pass — so no division is needed, and zeros are handled automatically.

Brute Force

TimeO(n²)SpaceO(1)

Intuition

For each index, multiply together every other element directly.

Algorithm

For each i:
- product = 1.
- For each j != i, product *= nums[j].
- answer[i] = product.
Return answer.

Visualization

nums = [1, 2, 3, 4]

i=0: 2·3·4 = 24
i=1: 1·3·4 = 12
i=2: 1·2·4 = 8
i=3: 1·2·3 = 6

Code

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]; // skip the element itself
                }
            }
            answer[i] = product;
        }
        return answer;
    }
}

Complexity

Time: O(n²) — n - 1 multiplications for each of the n positions.
Space: O(1) — besides the output array.

Prefix and Suffix Arrays

TimeO(n)SpaceO(n)

Intuition

Precompute two helper arrays: prefix[i] = product of nums[0..i-1] and suffix[i] = product of nums[i+1..n-1]. Then answer[i] = prefix[i] * suffix[i]. The empty product (nothing to the left of index 0, nothing to the right of the last index) is 1.

Algorithm

prefix[0] = 1; for i = 1..n-1, prefix[i] = prefix[i-1] * nums[i-1].
suffix[n-1] = 1; for i = n-2..0, suffix[i] = suffix[i+1] * nums[i+1].
answer[i] = prefix[i] * suffix[i].

Visualization

i	0	1	2	3
nums	1	2	3	4
prefix	1	1	2	6
suffix	24	12	4	1
answer	24	12	8	6

Code

java

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

        prefix[0] = 1; // nothing to the left of index 0
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        suffix[n - 1] = 1; // nothing to the right of the last index
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

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

Complexity

Time: O(n) — three linear passes.
Space: O(n) — the prefix and suffix arrays.

Single Output ArrayOptimal

TimeO(n)SpaceO(1)

Intuition

We do not need separate arrays. First store the prefix products directly in answer. Then sweep from the right with a single running variable suffix, multiplying it into answer[i] before folding nums[i] into it. The output array does double duty, leaving only O(1) extra space.

Algorithm

answer[0] = 1; for i = 1..n-1, answer[i] = answer[i-1] * nums[i-1] (prefix products).
suffix = 1.
For i = n-1 down to 0:
- answer[i] *= suffix.
- suffix *= nums[i].
Return answer.

Dry Run

flowchart TD
    A["nums = [1,2,3,4]"] --> B["Pass 1 (prefix)<br/>answer = [1,1,2,6]"]
    B --> C["i=3: answer[3] = 6·1 = 6<br/>suffix = 4"]
    C --> D["i=2: answer[2] = 2·4 = 8<br/>suffix = 12"]
    D --> E["i=1: answer[1] = 1·12 = 12<br/>suffix = 24"]
    E --> F["i=0: answer[0] = 1·24 = 24<br/>suffix = 24"]
    F --> G["return [24,12,8,6]"]

Code

java

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

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

        // Pass 2: multiply in the product of everything right of i
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffix;
            suffix *= nums[i]; // include nums[i] for the next index to the left
        }
        return answer;
    }
}

Complexity

Time: O(n) — two linear passes.
Space: O(1) — only the suffix variable beyond the required output array.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Prefix and Suffix Arrays	O(n)	O(n)
Single Output Array	O(n)	O(1) extra

Common Pitfalls

Using total-product-divided-by-nums[i] — it is forbidden, and it breaks on zeros (division by zero, or wrong answers when there are one vs. two zeros).
Updating suffix *= nums[i] before multiplying it into answer[i] — that includes the element itself.
Initialising the prefix/suffix with 0 instead of 1, which zeros out every product.
Off-by-one: prefix[i] must use nums[i-1], not nums[i].