Product Except Self

Question

You're given an array of integers. Return a new array such that each element at index i is the product of all elements in the original array except the one at i.

You must solve it in O(n) time and without using division.

Example

Input: [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Explanation: For index 0, product is 2×3×4 = 24, and so on.

Input: [2, 5, 1, 4]

Output: [20, 8, 40, 10]

Explanation: Exclude each element and multiply the rest.

My Notes

Use two passes: one from left to right, and one from right to left.
In first pass, store running products before each index.
In second pass, multiply with running product after each index.
Time: O(n), Space: O(n)

Visual Explanation

Input: [1, 2, 3, 4]

Step 1: Left-to-Right Product
leftToRight = [
  1,
  1×2 = 2,
  2×3 = 6,
  6×4 = 24
] => [1, 2, 6, 24]

Step 2: Right-to-Left Product
rightToLeft = [
  24×1 = 24,
  12×2 = 24,
  3×4 = 12,
  4
] => [24, 24, 12, 4]

Step 3: Final Output (excluding self)
output = [
  rightToLeft[1]                  = 24,
  leftToRight[0] × rightToLeft[2] = 1 × 12 = 12,
  leftToRight[1] × rightToLeft[3] = 2 × 4 = 8,
  leftToRight[2]                  = 6
] => [24, 12, 8, 6]

Final Output: [24, 12, 8, 6]

package main

import (
	"fmt"
)

func main() {
	result := productExceptSelf([]int{1, 2, 3, 4})
	fmt.Println(result)
}

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

	leftToRight := make([]int, n)
	rightToLeft := make([]int, n)

	for i := 0; i < n; i++ {
		if i == 0 {
			leftToRight[i] = nums[i]
		} else {
			leftToRight[i] = leftToRight[i-1] * nums[i]
		}
	}

	for i := n - 1; i >= 0; i-- {
		if i == n-1 {
			rightToLeft[i] = nums[i]
		} else {
			rightToLeft[i] = rightToLeft[i+1] * nums[i]
		}
	}

	for i := 0; i < n; i++ {
		if i == 0 {
			nums[i] = rightToLeft[i+1]
		} else if i == n-1 {
			nums[i] = leftToRight[i-1]
		} else {
			nums[i] = leftToRight[i-1] * rightToLeft[i+1]
		}
	}

	return nums
}