LeetCode 238. Product of Array Except Self

The Problem

Link to original problem on Leetcode.

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.

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

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

My Solution

Ignoring the Instructions

This would be fairly easy without the caveat “without using the division operation”. If division were allowed, you could just compute the product of all nums values and then return nums.map(num => numsProduct / num).¹ But alas, we must do something more complicated.

Bad Solution

Instead of computing total product and dividing by each value, we can compute the product of all the values to the left and all the values on the right and then multiply those.

const productExceptSelf = nums => {
	return nums.map((_, i) => {
		return product(nums.slice(0, i)) * product(nums.slice(i + 1));
	});
};

const product = nums => nums.reduce((prev, curr) => prev * curr, 1);

This is correct, but it is much too slow—it has $O(n{^2})$ time complexity. Leetcode will time out if you try this.

Better Solution

Computing the products to the left and right by multiplying all of those numbers each time is inefficient. Instead, we can store the result of each previous computation and multiply it by the most recent relevant number only as we move through the nums array. We’ll store these values as the prefix array and the suffix array. Since we no longer check each value to the left and right, this brings us down to $O(n)$ time complexity.

const productExceptSelf = nums => {
	let prefix = [];
	let suffix = [];
	let answer = [];

	// Compute the prefix values by multiplying whatever the previous prefix is by the number to the immediate left of nums[i]
	for (let i = 0; i < nums.length; i++) {
		if (i > 0) {
			prefix[i] = prefix[i - 1] * nums[i - 1];
		} else {
			prefix[i] = 1;
		}
	}

	// Loop backwards to compute the suffix values by multiplying the last suffix value computed by the number to the immediate right of nums[i]
	for (let i = nums.length - 1; i >= 0; i--) {
		if (i === nums.length - 1) {
			suffix[i] = 1;
		} else {
			suffix[i] = suffix[i + 1] * nums[i + 1];
		}
	}

	// Finally, fill in the answer array by multiplying prefixes and suffixes
	for (let i = 0; i < nums.length; i++) {
		answer[i] = prefix[i] * suffix[i];
	}

	return answer;
};

Still Better Solution

The previous solution works, but isn’t as space efficient as it could be. We don’t actually need to store prefix and suffix arrays at all!

const productExceptSelf = nums => {
	// First, initialize the answer array with length equal to nums' length and all values equal to 1.
	const answer = Array.from({ length: nums.length }, () => 1);

	// Next, we reset the values in the answer array to serve as our prefix array. Each answer[i] will be equal to the product of all values in nums.slice(0, i).
	for (let i = 1; i < nums.length; i++) {
		answer[i] = answer[i - 1] * nums[i - 1];
	}
	// Finally, we loop backwards to simultaneously update the answer values with suffix products and compute those suffix products. We reduce space complexity by keeping our computations in the answer array rather than storing separate prefix and suffix arrays.
	for (let j = nums.length - 1, suffix = 1; j >= 0; j--) {
		answer[j] *= suffix;
		suffix *= nums[j];
	}
	return answer;
};

Amazing Solution

Can we still improve? Yes! We don’t need two separate loops for computing the prefixes and suffixes while filling out the answer array.

const productExceptSelf = nums => {
	const answer = Array.from({ length: nums.length }, () => 1);

	for (let i = 0, prefix = 1, suffix = 1; i < nums.length; i++) {
		answer[i] *= prefix;
		prefix *= nums[i];
		answer[nums.length - 1 - i] *= suffix;
		suffix *= nums[nums.length - 1 - i];
	}

	return answer;
};