Product of Array Except Self


#1

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)


#2

The algorithm uses the below logic,

  1. Calculate the product of all elements left to an element.
  2. Calculate the product of all elements to right
// We traverse the array twice. 
// First time, assign the result[i] as the product of all left side values except itself.
// Sencod time, multiply the current value with the right side values of the element.

func productExceptSelf(nums []int) []int {
    result := make([]int, len(nums))
    for i:=0; i<len(result); i++{
        result[i] = 1
    }
    
    left := 1
    for i:=0;i<len(nums);i++{
        result[i] = result[i]*left
        left = left*nums[i]
    }
    
    right := 1
    for i:=len(nums)-1;i>=0;i--{
        result[i] = result[i]*right
        right = right*nums[i]
    }
    
    return result
}