# #12 Array Of Products

###### tags:`Array` `Medium`

## Problem


<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(n) space - where n is the length of the input array

:::

<br>

:::spoiler Hints


:::

<br>

<hr/>

## Solutions

### Official Solution 1

// O(n) time | O(n) space - where n is the length of the input array
function arrayOfProducts(array) {
    const products = new Array(array.length).fill(1);
    const leftProducts = new Array(array.length).fill(1);
    const rightProducts = new Array(array.length).fill(1);

    let leftRunningProduct = 1;
    for(let i = 0; i < array.length; i++) {
        leftProducts[i] = leftRunningProduct;
        leftRunningProduct *= array[i];
    }
    
    let rightRunningProduct = 1;
    for(let i = array.length; i > -1; i--) {
        rightProducts[i] = rightRunningProduct;
        rightRunningProduct *= array[i];
    }
    
    for(let i = 0; i < array.length; i++) {
        products[i] = leftProducts[i] * rightProducts[i];
    }
    
    return products;
}

<br>

### Official Solution 2

// O(n) time | O(n) space - where n is the length of the input array
function arrayOfProducts(array) {
    const products = new Array(array.length).fill(1);

    let leftRunningProduct = 1;
    for(let i = 0; i < array.length; i++) {
        leftProducts[i] = leftRunningProduct;
        leftRunningProduct *= array[i];
    }
    
    let rightRunningProduct = 1;
    for(let i = array.length; i > -1; i--) {
        products[i] = rightRunningProduct;
        rightRunningProduct *= array[i];
    }
    
    return products;
}

<br>

---

### Everyone's

使用 Map 與 Nested loop
:::spoiler Hao

/**
 * Time complexity: O(n) which n is array.length
 * Space complexity: O(n) which n is array.length
 */

function arrayOfProducts(array) {
    const products = new Map();

    for (let i = 0; i < array.length; i += 1) {
        products.set(i, undefined);
    }

    for (let i = 0; i < array.length; i += 1) {
        for (const [key, value] of products.entries()) {
            if (key === i) continue;
            else {
                if (value === undefined) products.set(key, array[i]);
                else products.set(key, value * array[i]);
            }
        }
    }
    
    return Array(products.size).fill().map((_, i) => products.get(i));
}

Hao: 想特別討論 Map 遍歷的 time complexity，應該不會變成 O(n^2) 嗎?
東: 我覺得會是 `O(n^2)`，因為 Object.entries 取出的就是一個 array, 所以仍然是在 loop array
其他人: ?
:::

<br>

三個 for loop，取 left products, right products 和 result
:::spoiler 東

function arrayOfProducts(array) {
  let leftCurrProduct = 1;
  let rightCurrProduct = 1;
  const leftOfIdxProduct = [];
  const rightOfIdxProduct = [];
  const result = [];

  for(let i = 0; i < array.length; i++){
    leftOfIdxProduct.push(leftCurrProduct);
    leftCurrProduct *= array[i];
  }

  for(let i = array.length - 1; i >= 0; i--){
    rightOfIdxProduct.unshift(rightCurrProduct);
    rightCurrProduct *= array[i]
  }

  for(let i = 0; i < array.length; i++){
    result.push(leftOfIdxProduct[i] * rightOfIdxProduct[i])
  }

  return result;
}

:::

<br>

與 official Solution 2 很像
:::spoiler 月

/*
    Time: O(n), Space: O(1)
    n is the length of array.
*/
function arrayOfProducts(array) {
    const { length } = array;
    const result = [...Array(length).fill(1)];
    for (let i = 1; i < length; i++) {
        result[i] = result[i - 1] * array[i - 1];
    }
    let right = 1;
    for (let i = length - 1; i >= 0; i--) {
        result[i] *= right;
        right *= array[i];
    }
    return result;
}

:::

:::spoiler YC

/*
  time: O(2n) - where n is the length of the given array
  space: O(n) - where n is the length of the given array
*/
function arrayOfProducts(array) {
  const len = array.length;
  const ans = Array(len).fill(0);
  let product = 1;
  for(let i = 0; i < len; i++){
    ans[i] = product;
    product *= array[i]; 
  }
  
  product = 1;
  for(let i = len - 1; i >= 0; i--){
    ans[i]*= product;
    product *= array[i]; 
  }

  return ans;
}

:::

<br>

---

## Supplement / Discussion