Product of Array Except Self


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


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


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