Product of Array Except Self

• https://leetcode.com/problems/product-of-array-except-self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Solution1: Time Complexity O(N), Space Complexity O(N)

We could construct two arrays, one scan from the input array from left to right, and another scan from left to right.

Left array(sumArray)

• (1)1 (1*1)2 (1*2)3 (1*2*3)4

Right array(sumArrayReverse)

• 1(2*3*4) 2(3*4) 3(4*1) 4(1)

/**
 * Time complexity: O(N).
 * Space complexity: O(N).
 */
public int[] productExceptSelf(int[] nums) {
    int sum = 1;
    int[] sumArray = new int [nums.length];
    int[] sumArrayReverse = new int [nums.length];
    int[] result = new int [nums.length];

    sumArray[0] = 1;
    sumArrayReverse[nums.length - 1] = 1;

    for (int i = 0; i < nums.length - 1; i++) {
        sumArray[i + 1] = sumArray[i] * nums[i];
    }

    for (int i = nums.length - 1; i > 0; i--) {
        sumArrayReverse[i - 1] = sumArrayReverse[i] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        result[i] = sumArray[i] * sumArrayReverse[i];
    }

    return result;
}

Solution 2: Reduce space complexity to O(1)

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

    result[nums.length - 1] = 1;

    for (int i = nums.length - 1; i > 0; i--) {
        result[i - 1] = result[i] * nums[i];
    }

    int left = 1;
    for (int i = 0; i < nums.length; i++) {
        result[i] = result[i] * left;
        left = left * nums[i];
    }

    return result;
}