Product of Array Except Self

Given an array nums, return an array answer where answer[i] is the product of every element of nums except nums[i]. Don't use division, and aim for O(n) time.

LeetCode: 238. Product of Array Except Self

Example 1

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

Example 2

Input:  [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: every product that includes the 0 is 0. Only answer[2] skips it: -1*1*-3*3 = 9.

Brute force: multiply everything else

For every index i, loop over the whole array and multiply every element whose index is not i.

import java.util.Arrays;

public class Main {
    static int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        Arrays.fill(answer, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (j != i) {
                    answer[i] *= nums[j];
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(productExceptSelf(new int[]{1, 2, 3, 4})));
        System.out.println(Arrays.toString(productExceptSelf(new int[]{-1, 1, 0, -3, 3})));
    }
}

[24, 12, 8, 6]
[0, 0, 9, 0, 0]

Time: O(n²). Space: O(1) besides the output.

Why not divide?

The obvious O(n) idea is total_product / nums[i]. It fails in two ways:

• If nums[i] == 0, integer division throws ArithmeticException.
• If there's a zero anywhere, total_product is 0, and dividing it can't recover the product of the other elements.

You can patch this by counting zeros, but the problem forbids division anyway.

Optimal: prefix products times suffix products

Split the answer at index i into two parts:

answer[i] = (product of nums[0..i]) * (product of nums[i+1..])
          =        prefix[i]        *        suffix[i]

For [1, 2, 3, 4]:

Both columns can be built with a running product. To avoid allocating separate prefix and suffix arrays:

1. Left to right: write the prefix product into answer[i], then multiply the running product by nums[i].
2. Right to left: multiply answer[i] by a running suffix product, then multiply the suffix by nums[i].

import java.util.Arrays;

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

        int prefix = 1;
        for (int i = 0; i < n; i++) {
            answer[i] = prefix;      // product of nums[0..i)
            prefix *= nums[i];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffix;     // times product of nums[i+1..n)
            suffix *= nums[i];
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(productExceptSelf(new int[]{1, 2, 3, 4})));
        System.out.println(Arrays.toString(productExceptSelf(new int[]{-1, 1, 0, -3, 3})));
        System.out.println(Arrays.toString(productExceptSelf(new int[]{0, 0, 5})));
    }
}

[24, 12, 8, 6]
[0, 0, 9, 0, 0]
[0, 0, 0]

Time: O(n): two passes. Space: O(1) extra, because the output array does not count and the only other state is two integers.

Edge cases

• One zero: only the zero's own position gets a non-zero product.
• Two or more zeros: every answer is 0.
• Negative numbers: handled by normal multiplication.
• Overflow: LeetCode guarantees every prefix and suffix product fits in an int. For arbitrary input, int multiplication wraps silently; use long or Math.multiplyExact, which throws ArithmeticException on overflow.