Product of Array Except Self
MediumThe problem
Given a list of numbers nums, return a new list where each position i holds the product of all the numbers in nums except nums[i]. Do not use division.
- Example 1Input: nums = [1, 2, 3, 4]Output: [24, 12, 8, 6]
For position 0: 2 × 3 × 4 = 24. For position 1: 1 × 3 × 4 = 12. For position 2: 1 × 2 × 4 = 8. For position 3: 1 × 2 × 3 = 6.
- Example 2Input: nums = [-1, 1, 0, -3, 3]Output: [0, 0, 9, 0, 0]
The only position without the 0 in its product is position 2: -1 × 1 × -3 × 3 = 9. All other products include the 0.
- 2 ≤ nums.length ≤ 100,000
- -30 ≤ nums[i] ≤ 30
- Every product fits in a 32-bit integer
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Division is not allowed. The product of everything else = (everything to the left) × (everything to the right).
The idea
Pass 1 left→right stores the running product of the left side in the result; pass 2 right→left multiplies in a running product of the right side.
Target: O(n) time, O(1) extra space
Go function shape
func productExceptSelf(nums []int) []intReference solution
Tested with go test. Try it yourself first, then compare.
// ProductExceptSelf: out[i] = product of every element except nums[i], no division.
// A prefix PRODUCT from the left, then a suffix product from the right.
func ProductExceptSelf(nums []int) []int {
out := make([]int, len(nums))
run := 1
for i := range nums {
out[i] = run // product of everything left of i
run *= nums[i]
}
run = 1
for i := len(nums) - 1; i >= 0; i-- {
out[i] *= run // multiply by everything right of i
run *= nums[i]
}
return out
}