problem

輸入為一陣列，陣列不為空且元素皆為整數。輸出一個長度相同的新陣列，其中每個位置 i 為輸入陣列 i 位置以外的元素乘積。

sample input:
array = [5, 1, 4, 2]

sample output:
[8, 40, 10, 20]

// output[0] 為 array[1] * array[2] * array[3]
// output[1] 為 array[0] * array[2] * array[3]
// output[2] 為 array[0] * array[1] * array[3]
// output[3] 為 array[0] * array[1] * array[2]

solution 01

第一種是暴力解，以兩層迴圈計算每個位置的結果。當內層迴圈的數字和外層不同時，就乘上該數字。

n 為輸入陣列長度，
time: O(n^2)
space: O(n) 來自輸出陣列。

function arrayOfProducts(array) {
  const products = [];
  for (let i = 0; i < array.length; i++) {
    let product = 1;
    for (let j = 0; j < array.length; j++) {
      if (i !== j) {
        product *= array[j];
      }
    }
    products[i] = product;
  }
  return products;
}

solution 02

第二種解法嘗試減少重複的計算。想法是，每個output[i]，可以理解為 input[i]左邊數字的乘積 * input[i]右邊數字的乘積，所以如果記錄每個位置左邊和右邊的乘積，最終再相乘就可以得到結果。
步驟是：

1. 輸入陣列 array 之外，建立兩個陣列，每個位置 i 分別要填入 array[i] 的左邊乘積和右邊乘積。
   array = [5, 1, 4, 2]
   left = [1, 1, 1, 1]
   right = [1, 1, 1, 1]
2. 初始化變數 product = 1。left 陣列從左邊開始，每個 left[i] 先填入 product，接著更新 product = product * array[i]。
   結束後，left = [1, 5, 5, 20]
3. 接著 right 陣列從右邊開始，重複步驟 2。
   結束後，right = [8, 8, 2, 1]
4. 將 left 和 right 對應位置 i 的數字相乘，即為 output[i]。

n 為輸入陣列長度，
time: O(n) 得出左、右、輸出陣列各需要 n 時間。
space: O(n) 左、右、輸出陣列各需要 n 空間。

function arrayOfProducts(array) {
  const products = new Array(array.length).fill(1);
  const left = new Array(array.length).fill(1);
  const right = new Array(array.length).fill(1);

  let leftProduct = 1;
  for (let i = 0; i < array.length; i++) {
    left[i] = leftProduct;
    leftProduct *= array[i];
  }

  let rightProduct = 1;
  for (let i = array.length - 1; i > -1; i--) {
    right[i] = rightProduct;
    rightProduct *= array[i];
  }

  for (let i in array) {
    products[i] = left[i] * right[i];
  }
    
  return products;
}

solution 03

第三種解進一步簡化第二種解，也就是將左、右、輸出三個陣列改成只用一個陣列。

作法與解二的差異在於，得出左邊乘積 left = [1, 5, 5, 20] 之後，計算右邊乘積時直接相乘，不再新增陣列。

這種解的時間和空間複雜度和解二一樣，只是減少一次迴圈並減少兩個額外的陣列空間。

function arrayOfProducts(array) {
  const products = new Array(array.length).fill(1);

  let leftProduct = 1;
  for (let i = 0; i < array.length; i++) {
    products[i] = leftProduct;
    leftProduct *= array[i];
  }

  let rightProduct = 1;
  for (let i = array.length - 1; i >= 0; i--) {
    products[i] *= rightProduct;
    rightProduct *= array[i];
  }
    
  return products;
}