238. Product of Array Except Self

Medium

Array Prefix Sum

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^5
-30 <= nums[i] <= 30
The input is generated such that answer[i] 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.)

func productExceptSelf(nums []int) []int {
    product := 1
    zeroes := 0
    for _, num := range nums {
        if num != 0 {
          product *= num
        } else {
          zeroes++
        }
    }
    if zeroes > 1 {
        product = 0
    }

    result := make([]int, len(nums))
    for i, num := range nums {
        if num != 0 {
            result[i] = product / num
            if zeroes > 0 {
              result[i] = 0
            }
        } else {
            if zeroes == 1 {
              result[i] = product
            }

        }
    }

    return result
}

💡 Hints (2)

Hint 1

Think how you can efficiently utilize prefix and suffix products to calculate the product of all elements except self for each index. Can you pre-compute the prefix and suffix products in linear time to avoid redundant calculations?

Hint 2

Can you minimize additional space usage by reusing memory or modifying the input array to store intermediate results?