#4 Product of Array Except Self

#4 Product of Array Except Self

Blind 75. Array.

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

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]

Before we jump into solving this product, let's first take our time and discuss where we need to use this algorithm in the real world? why bother to learn it anyways?

Real world use of this algorithm:

1.  Financial Analysis:
2. Portfolio Impact: Calculating portfolio performance excluding a specific stock.
3. Image Processing and Computer Vision
4. Filter Application: When applying filters to images, sometimes you need to calculate the effect of excluding a particular pixel or region. This can be useful in edge detection, smoothing, or other image processing tasks.
5. Object Removal: In scenarios where you want to remove an object from an image and analyze the background, calculating the effect of excluding the object's pixels can be useful.
6. E-commerce
7. User Behavior: understanding the impact of excluding a particular user's behavior can help in refining the recommendation algorithm
8. Product Impact:  understanding the impact of excluding a particular product can help in inventory management and sales analysis. This can help in identifying key products that drive sales.

Now let's see how we can solve this?

1. Brute force approach. Without thinking about optimisation, let's first come up with the solution.

function bruteForceApproach(nums) {

  let output = []

  for (let i = 0; i < nums.length; i++) {

    // calculating product for i

    let product = 1

    for (let j = 0; j < nums.length; j++) {

      if (i !== j) {

        product *= nums[j]

      }

    }

    output[i] = product

  }

  return output

}

has a time complexity of O(N*N), which does not meet the requirement of O(N)

What's the problem?

Main problem is redundant calculation. For each element in the output array, it recalculated the product of all the other elements, even though some of the product could have been reused from previous calculations. 

*******  Brainstorming *******

 To optimize the solutions in O(N), we need to find a way to avoid the redundant calculations and reuse the intermediate results as much as possible. 

Oneway to calculate the product of array @ i, without i = prefix(i) * postfix(i)

1. Calculate Left Products:
2.  Traverse the product from left to right and compte the product of all elements to the left of each element
3. prefix[i] = nums[i -1] * prefix[i-1]
4. Calculate Right Products:
5. Traverse the array from right to left, compute the product of all elements to the right of each element. 
6.   postfix[i] = nums[i + 1] * prefix[i+1]
7. Combine Left and Right Products
8.  By multiplying left[i] * right[i]

function optimized(nums){

  let prefix = []

  let postfix = []

  let len = nums.length

  //there is no prefix to 0, so

  prefix[0] = 1

  //@ postfix , no element to the right of last element so 1

  // array is valid from 0 to n-1

  postfix[len - 1] = 1

  //calculating prefix

  for (let i = 1; i < len; i++){

    prefix[i] = nums[i - 1] * prefix [i -1]

  }

  // calculating postfix

  //also to account for n-1, which is last element to the right

  for(let i = len -2; i>=0; i--){

    postfix[i] = nums[i+1] * postfix[i + 1]

  }

  let finalResult = []

  for(let i = 0; i < len; i++){

    finalResult[i] = prefix[i] * postfix[i]

  }

  return finalResult

}

This is the result in leetcode.

here there is prefix and postFix array, let's see if can further optimize this solution to just use result array to save more space.

function futherOptimized(nums){

  let productLHS = 1

  let result = []

  for(let i = 0; i < nums.length; i++){

    result[i] = productLHS 

    productLHS *=nums[i]

  }

  let productRHS = 1

  for(let i = nums.length -1; i >=0; i--){

    result[i] *= productRHS 

    productRHS *=nums[i]

  }

  return result

}

here we have more optimized result.

So this is how this array problem can be solved and further optimized