# Leetcode - product of array except self

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

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).


Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

My solution

public class ProductExceptSelf {
/**
* Approach 1:- Find the left[i] at i containing all the left multiplication. Do same with right[i]
*/
public int[] productExceptSelf(int[] nums) {

int size = nums.length;

int[] output = new int[size];
int[] left = new int[size];
int[] right = new int[size];

int temp = 1;
// Start filling up left array
for (int i = 0; i < size; i++) {
left[i] = temp;
temp = temp * nums[i];
}

// Again set the temp to 1
temp = 1;

// Start filling up right array
for (int i = size - 1; i >= 0; i--) {
right[i] = temp;
temp = temp * nums[i];
}

// Final traversal and return sum array.
for (int i = 0; i < size; i++) {
output[i] = left[i] * right[i];
}

return output;
}
}


Every time you feel obliged to put a comment like

    // Start filling up left array


you really deal with a potentially important algorithm, which deserves a name, and a method of its own. In this case the algorithm is known as partial product. Consider factoring it out, and see the comments disappear.

Ditto for the second loop.

Regarding space complexity,

• You don't need left: accumulate the partial products directly into output.

• You don't need right as well: instead of accumulating the partial products, use it immediately:

    temp = 1;

for (int i = size - 1; i >= 0; i--) {
output[i] *= temp;
temp = temp * nums[i];
}