Product of Array Except Self#

Given an array of integers, return a new array where each position holds the product of every other element in the original array. You must solve it without using the division operator, and the answer for each element fits in a standard integer.

Example#

Input: nums = [1, 2, 3, 4] Output: [24, 12, 8, 6]. For index 0 the product of the rest is 2 * 3 * 4 == 24, and so on.

Brute force#

For each index, loop over the whole array and multiply all the other values. This recomputes overlapping work again and again.

• Time: O(n^2).
• Space: O(1) beyond the output.

Optimal approach#

For each index, the answer is the product of everything to its left times the product of everything to its right. Do two passes. First sweep left to right, storing the running prefix product for each index. Then sweep right to left, multiplying each position by the running suffix product. Because you carry the suffix in a single variable, no division is needed and only the output array is extra space.

Python solution#

 1def product_except_self(nums):
 2    n = len(nums)
 3    result = [1] * n
 4
 5    prefix = 1
 6    for i in range(n):
 7        result[i] = prefix
 8        prefix *= nums[i]
 9
10    suffix = 1
11    for i in range(n - 1, -1, -1):
12        result[i] *= suffix
13        suffix *= nums[i]
14
15    return result

Complexity#

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

This problem is a prefix and suffix product variant of the hashing and array patterns. Keep building with the 60-day challenge.