Product of Array Except Self

Problem Statement

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

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]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Golang Code

func productExceptSelf(nums []int) []int {
	totalProduct := 1
	totalZero := 0

	// Calculate the product of all non-zero elements and count the number of zeros
	for _, val := range nums {
		if val != 0 {
			totalProduct *= val
		} else {
			totalZero += 1
		}
	}

	for i, val := range nums {
		if totalZero >= 2 {
			// If there are two or more zeros, all products except self are zero
			nums[i] = 0
		} else if totalZero == 1 {
			// If there's exactly one zero, only the position of zero in the original array will have a non-zero product
			if val == 0 {
				nums[i] = totalProduct
			} else {
				nums[i] = 0
			}
		} else {
			// If there are no zeros, calculate the product except self by dividing the total product by the current element
			nums[i] = totalProduct / val
		}
	}

	return nums
}

Better version

func productExceptSelf(nums []int) []int {
	totalProduct := 1
	totalZero := 0

	// Calculate the product of all non-zero elements and count the number of zeros
	for _, val := range nums {
		if val != 0 {
			totalProduct *= val
		} else {
			totalZero += 1
		}
	}

	for i, val := range nums {
		if totalZero >= 2 {
			// If there are two or more zeros, all products except self are zero
			nums[i] = 0
		} else if totalZero == 1 {
			// If there's exactly one zero, only the position of zero in the original array will have a non-zero product
			if val == 0 {
				nums[i] = totalProduct
			} else {
				nums[i] = 0
			}
		} else {
			// If there are no zeros, calculate the product except self by dividing the total product by the current element
			nums[i] = totalProduct / val
		}
	}

	return nums
}

Optimised version

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

The approach in the productExceptSelf function you provided is more efficient and generally better than the first approach for solving the “Product of Array Except Self” problem. Here’s why:

Explanation of the Provided Function

Initialization:
- productExceptSelf is initialized as an array of the same length as nums, with the first element set to 1.
Left Product Calculation:
- The first loop computes the product of all elements to the left of each element in the array. This is stored in productExceptSelf.
- productExceptSelf[i] at the end of this loop contains the product of all elements before nums[i].
Right Product Calculation:
- The second loop iterates from the rightmost element to the leftmost.
- right keeps track of the product of all elements to the right of the current element.
- productExceptSelf[i] is updated by multiplying it with right, which now represents the product of all elements to the right of nums[i].
Final Output:
- The productExceptSelf array now contains the product of all elements except the current one for each position.

Complexity

Time Complexity: O(n)
- The function iterates through the list twice, once for the left product and once for the right product, leading to a linear time complexity.
Space Complexity: O(1) (if we exclude the output array productExceptSelf).
- The only extra space used is for the output array productExceptSelf and a single variable right. This is constant space relative to the size of the input.

Comparison with the First Approach

Efficiency:
- The provided approach does not involve division, avoiding issues related to division by zero and eliminating the need to handle zero elements separately.
- The first approach, which computes the total product and handles zeros, is less efficient as it requires conditional checks and multiple iterations with potential divisions.
Simplicity:
- The provided approach is conceptually simpler. It methodically builds the product from both directions (left and right) without special case handling.
Edge Cases:
- The approach inherently handles all edge cases, including those with zeros in the input, without any additional logic.

Conclusion

The productExceptSelf function provided is better in terms of efficiency, simplicity, and robustness. It’s a widely recognized optimal solution for the “Product of Array Except Self” problem, using an elegant two-pass approach with linear time complexity and minimal space usage.

CODE & ALGO