LeetCode - 238. Product of Array Except Self

Thoughts:

I choose prefix sum to solve this problem. And I can find the product of array except self by checking the left product and right product. The time complexity will be O(n).

Thoughts visuzlization:

origin: [1,2,3,4]

i = 0, left: not exists, so 1

i = 1, left: 1

i = 2, left: 1 * 2

i = 3, left: 1 * 2 * 3

left: [1,1,2,6]

i = 3, right: not exists, so 1

i = 2, right: 4

i = 1, right: 4 * 3

i = 0, right: 4 * 3 * 2

right: [24,12,4,1]

then do left[i] * right[i] for each i

answer: [24,12,8,6]

Code:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const length = nums.length;
  const leftProducts = new Array(length).fill(1);
  const rightProducts = new Array(length).fill(1);
  const answer = [];
  for (let i = 1; i < length; i++) {
    leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
  }
  for (let i = length - 2; i >= 0; i--) {
    rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
  }
  for (let i = 0; i < length; i++) {
    answer.push(leftProducts[i] * rightProducts[i]);
  }
  return answer;
};

Reference

Original link

Basic prefix sum