Product of Array Except Self

Problem

Given an array nums, return an array output where output[i] is the product of all elements of nums except nums[i]. Solve it without division and in O(n) time.

Example

[1, 2, 3, 4]  ->  [24, 12, 8, 6]

Go Solution

package main

import "fmt"

func productExceptSelf(nums []int) []int {
    n := len(nums)
    out := make([]int, n)

    prefix := 1 // product of everything to the left of i
    for i := 0; i < n; i++ {
        out[i] = prefix
        prefix *= nums[i]
    }

    suffix := 1 // product of everything to the right of i
    for i := n - 1; i >= 0; i-- {
        out[i] *= suffix
        suffix *= nums[i]
    }
    return out
}

func main() {
    fmt.Println(productExceptSelf([]int{1, 2, 3, 4})) // [24 12 8 6]
}

How to Solve

1. Each answer is left-product × right-product. output[i] equals the product of everything before i times the product of everything after i — which never includes nums[i] itself, so no division is needed.
2. First pass (left to right): fill out[i] with the running product of all earlier elements (prefix), then fold nums[i] into prefix.
3. Second pass (right to left): multiply each out[i] by the running product of all later elements (suffix), then fold nums[i] into suffix.
4. Output doubles as scratch space, so no extra arrays are needed beyond the result.

Complexity

Time: O(n), two linear passes. Space: O(1) extra (the output array aside).