238. Product of Array Except Self

Description

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.

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]

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

My Solution

 
// Failed: Time Limit Exceeded 
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let answer = [];
  for (let i = 0; i < nums.length; i++) {
    let total = 1;
    for (let j = 0; j < nums.length; j++) {
      if (i !== j) {
        total *= nums[j];
      }
    }
    answer.push(total);
  }
  return answer
}

Solution from others

 
// prefix product * suffix product === product of all elements except self
// Time complexity: O(n)
 
var productExceptSelf = function(nums) {
    const n = nums.length;
    const answer = new Array(n);
    answer[0] = 1;
 
    // Calculate the product of all elements to the left of each element
    for (let i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
 
    let rightProduct = 1;
    // Calculate the product of all elements to the right of each element 
    // and multiply it with the previously computed product from the left
    for (let i = n - 1; i >= 0; i--) {
        answer[i] *= rightProduct;
        rightProduct *= nums[i];
    }
 
    return answer;
};

151. Reverse Words in a String 283. Move Zeroes