Product of Array Except Self

Question

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]. Note: Please solve it without division and in O(n).

Example

Input:  [1,2,3,4]
Output: [24,12,8,6]

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.)

Solution

Since we couldn’t use division during the process, so we have to calculate the mutiples before the current element and also calculate the multiples after that, and then multiples for final results.

Code

// time:O(n) space:O(n)
public int[] productExceptSelf(int[] nums) {
       int n = nums.length;
       if (nums == null || n == 0) return new int[]{};
       int[] forward = new int[n];
       int[] backward = new int[n];
       forward[0] = 1;
       backward[n - 1] = 1;
       // first pass
       for (int i = 1; i < n; i++) {
           forward[i] = forward[i - 1] * nums[i - 1];
       }
       // second pass
       for (int i = n - 2; i >= 0; i--) {
           backward[i] = backward[i + 1] * nums[i + 1];
       }
       
       for (int i = 0; i < n; i++) {
           forward[i] *= backward[i];
       }
       return forward;
   }

// time:O(n) space:O(1)
public int[] productExceptSelf(int[] nums) {
       int n = nums.length;
       if (nums == null || n == 0) return new int[]{};
       int[] forward = new int[n];
       int backward = 1;
       forward[0] = 1;
       
       for (int i = 1; i < n; i++) {
           forward[i] = forward[i - 1] * nums[i - 1];
       }
       
       for (int i = n - 2; i >= 0; i--) {
           backward *= nums[i + 1];
           forward[i] *= backward;
       }
       
       return forward;
   }