LeetCode 238.

Question

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Intuition

answer[i] = nums[0] * … * nums[i-1] * numx[i+1] * … * nums[n-1]

Approach

Divide the product answer[i] by left[i-1] times right[i+1]:

left[i-1] = nums[0] * nums[1] * … * nums[i-1]
right[i+1] = nums[i+1] * nums[i+2] * … * nums[n-1]

Complexity

Time complexity: O(n)
Space complexity: O(n)

Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left2Right = new int[nums.length]; // left2Right[i] = nums[0]*nums[1]*...*nums[i]
        int[] right2Left = new int[nums.length]; // right2Left[i] = nums[i]*nums[i+1]*...*nums[nums.length-1]
        left2Right[0] = nums[0];
        right2Left[nums.length-1] = nums[nums.length-1];
        for (int i=1; i<nums.length-1; i++) {
            left2Right[i] = left2Right[i-1] * nums[i];
        }
        for (int i=nums.length-2; i>0; i--) {
            right2Left[i] = right2Left[i+1] * nums[i];
        }
        int[] result = new int[nums.length];
        result[0] = right2Left[1];
        result[nums.length-1] = left2Right[nums.length-2];
        for (int i=1; i<nums.length-1; i++) {
            result[i] = left2Right[i-1] * right2Left[i+1];
        }
        return result;
    }
}

Check out the description of these two problems at LC 238.