Product of Array Except Self

NeetCode: Product of Array Except Self · LeetCode: 238. Product of Array Except Self · Difficulty: Medium

Return an array output where output[i] is the product of every element of nums except nums[i]. Do not use division, and aim for O(n) time.

Example

Text

Input:  nums = [1, 2, 4, 6]     Output: [48, 24, 12, 8]
Input:  nums = [-1, 0, 1, 2, 3] Output: [0, -6, 0, 0, 0]

Brute force: multiply everything else

For each index, multiply all the other elements.

Java

import java.util.Arrays;

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

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

Output

[48, 24, 12, 8]
[0, -6, 0, 0, 0]

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

Optimal: prefix and suffix products

The product except nums[i] is (product of everything to its left) times (product of everything to its right). Both can be built in the output array itself. A new int[n] starts filled with zeros, so each slot is written before it is multiplied:

Left to right, store in result[i] the product of nums[0] to nums[i - 1].
Right to left, keep a running suffix product and multiply it into result[i].

Java

import java.util.Arrays;

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

        int prefix = 1;
        for (int i = 0; i < n; i++) {
            result[i] = prefix;
            prefix *= nums[i];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }
        return result;
    }
}

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

Output

[48, 24, 12, 8]
[0, -6, 0, 0, 0]

Time: O(n). Space: O(1) beyond the output array.

A zero in the input zeroes every product except the one at the zero's own index, and the prefix/suffix method handles this without special cases. LeetCode guarantees that every prefix and suffix product fits in a 32-bit int. Without that guarantee, Java int multiplication wraps silently.