Product of Array Except Self

Given an integer array nums, return an array answer where answer[i] is the product of every element except nums[i]. It must run in O(n) without using division. The follow-up asks for O(1) extra space, not counting the output. This is LeetCode 238.

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

How to Think About It

Step 1: Why not divide?

Multiplying everything and dividing by nums[i] is not allowed, and it would also break on zeros.

Step 2: Split "everything except i" into two parts

Everything except nums[i] is the elements to its left times the elements to its right:

answer[i] = (product of nums[0..i-1]) × (product of nums[i+1..n-1])

Step 3: Left products, left to right

The product of everything left of i is the product left of i - 1, times nums[i - 1]. One pass fills these into answer, starting with 1 (nothing to the left of index 0).

Step 4: Right products, right to left, in a single variable

Walk back from the end, keeping right, the product of everything right of i. Multiply answer[i] by it, then fold nums[i] into right. No second array is needed, which meets the O(1) follow-up.

Walkthrough

nums = [1, 2, 3, 4].

iLeft productRight productanswer[i]
012 × 3 × 4 = 2424
113 × 4 = 1212
21 × 2 = 248
31 × 2 × 3 = 616

Java Solution

The first loop stores left products in answer; the second multiplies in the right products on the way back.

Java
import java.util.Arrays;

public class ProductOfArrayExceptSelf {

    public static 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];   // product of everything left of i
        }
        int right = 1;                                 // product of everything right of i
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= right;
            right *= nums[i];
        }
        return answer;
    }

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

The original implementation, ProductOfArrayExceptSelf.java, is on GitHub.

Complexity

  • Time: O(n): two passes.
  • Space: O(1) besides the output.

The same "everything to the left, everything to the right" split appears with sums in Find Pivot Index and with maximums in Trapping Rain Water.