Product of Array Except Self

1. Problem Description

Given an integer array nums of length n, where n > 1, return an output array output where output[i] equals the product of all elements in nums except nums[i].

2. Approach

1. Approach 1
   • Calculate the left and right product arrays separately
   • Left: L[3] = a[0] * a[1] * a[2], excluding the current number a[3]
   • Right: R[5] = a[6] * a[7] * a[8], excluding the current number a[5]
   • The result is L[x]*R[x]

3. Implementation

3.1. Two Pointers (Converging)

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

    right := make([]int, len(nums))
    right[len(nums)-1] = 1
    for i := len(nums)-1; i > 0; i--{
        right[i-1] = right[i] * nums[i]
    }

    res := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
        res[i] = left[i]*right[i]
    }
    return res
}

4. References

• 238. Product of Array Except Self - LeetCode