238. Product of Array Except Self

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 238

Problem Statement

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 <= 105
-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.)

Approach & Solution Steps

• 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 JS Solution

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;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.