238. Product of Array Except Self

Quick Identifier

• Topic: arrays-hashing
• Pattern: Prefix / Suffix Arrays (Two-Pass Accumulation)
• Hint: The product of an array except nums[i] is exactly equal to the product of everything to the left of i, multiplied by the product of everything to the right of i. Calculate the lefts, calculate the rights, then multiply them together.
• Difficulty: Medium
• Companies: Amazon, Meta, Google, Apple, Microsoft
• LeetCode: 238

Quick Sights

• Time Complexity: O(n). We do one pass left-to-right, and one pass right-to-left. $O(2n)$ simplifies to $O(n)$.
• Space Complexity: O(1) extra space. The problem explicitly states the output array does not count toward space complexity. We only use two integer variables to track the running products.
• Core Mechanism:
  1. Initialize an answer array with 1s.
  2. Forward Pass: Track a running prefix product. For each index, set answer[i] = prefix, then multiply prefix by nums[i].
  3. Backward Pass: Track a running suffix product. Traverse backward. For each index, multiply answer[i] by suffix, then multiply suffix by nums[i].

Concept Explanation

As a senior engineer, the "No Division" constraint is what elevates this from an Easy to a Medium.

1. The Division Trap: The naive math solution is to multiply every number together to get a totalProduct, then for each index, return totalProduct / nums[i]. This instantly fails if there are zeros in the array (divide by zero error).
2. The Prefix/Suffix Split: If you can't divide the whole, you must construct the parts. The product of an array excluding the current element is simply: (Product of all elements to the left) * (Product of all elements to the right).
3. The $O(n)$ Space Solution: You could make two new arrays: leftProducts and rightProducts. leftProducts[i] holds the product of everything left of i. You then multiply leftProducts[i] * rightProducts[i]. This works perfectly, but uses $O(n)$ extra space.
4. The $O(1)$ Space Optimization: Instead of creating a separate leftProducts array, write the left products directly into the final answer array. Then, instead of creating a rightProducts array, use a single suffix integer variable. Traverse the answer array backwards, multiplying the stored left product by the running suffix variable.

Diagram

This flowchart traces the two-pass accumulation strategy.

Study Pattern (SDE3+)

• 0–3 min: Immediately point out the division trap (zeros). Explain the concept of splitting the problem into left and right sub-arrays. Establish the $O(n)$ space solution first, then confidently declare you can optimize it to $O(1)$ space by using the output array to store the prefix products.
• Implementation pass: Be careful with the updates. You must assign ans[i] = prefix before you multiply prefix * nums[i]. If you multiply first, you are including the element itself in the product, violating the "except self" rule.
• 5 min extension: What if the array is massive and you want to parallelize this? You could calculate the prefix array on Thread A and the suffix array on Thread B simultaneously, then merge them in a final pass. This trades the $O(1)$ space optimization for a strict halving of wall-clock time via $O(n)$ extra space.

Approaches

• Division — Calculate total product, divide by nums[i]. Time: $O(n)$, Space: $O(1)$. Fails constraint, crashes on zeros.
• Two Arrays (Prefix + Suffix) — Time: $O(n)$, Space: $O(n)$.
• Optimized Two-Pass — Store prefix in output array, compute suffix on the fly. Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

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

	// Pass 1: Calculate prefixes and store directly in ans
	prefix := 1
	for i := 0; i < n; i++ {
		ans[i] = prefix
		prefix *= nums[i]
	}

	// Pass 2: Calculate suffixes on the fly and multiply with stored prefixes
	suffix := 1
	for i := n - 1; i >= 0; i-- {
		ans[i] *= suffix
		suffix *= nums[i]
	}

	return ans
}

JavaScript

function productExceptSelf(nums) {
	const n = nums.length;
	const ans = new Array(n);

	// Pass 1: Calculate prefixes
	let prefix = 1;
	for (let i = 0; i < n; i++) {
		ans[i] = prefix;
		prefix *= nums[i];
	}

	// Pass 2: Calculate suffixes and combine
	let suffix = 1;
	for (let i = n - 1; i >= 0; i--) {
		ans[i] *= suffix;
		suffix *= nums[i];
	}

	return ans;
}

Walkthrough

Input: nums = [1, 2, 3, 4]

Pass 1: Forward (Prefixes)

Pass 2: Backward (Suffixes)

Output: [24, 12, 8, 6]

Edge Cases

• One zero (e.g., [1, 2, 0, 4]). The position with the 0 will have a non-zero product (1 * 2 * 4 = 8). Every other position will correctly be 0 because it multiplied by the zero.
• Multiple zeros (e.g., [1, 0, 3, 0]). The prefix/suffix logic naturally guarantees every single element in the answer array will evaluate to 0.
• Negative numbers. Handled perfectly without requiring any change in logic.

Pitfalls

• Accidentally multiplying prefix by nums[i] before storing it.
• Initializing prefix or suffix to 0. They are multiplicative accumulators; they must be initialized to 1.

Similar Problems

• 560. Subarray Sum Equals K — The quintessential Prefix Sum problem.
• 42. Trapping Rain Water — Uses the exact same "Left Array vs Right Array" concept to calculate bounding heights.

Mind-Map Tags

#arrays #prefix-sum #two-pass #optimal-space #math