238. Product of Array Except Self

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

Constraints:

• You must write an algorithm that runs in O(n) time and without using the division operation.
• 2 <= nums.length <= 105
• 30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

The most finicky constraint is the ban on the division operator—otherwise, the solution would be very simple: simply calculate the product of the entire array, and for every answer[i], we calculate product / nums[i]. Without division, however, we must build the answers from scratch.

A naïve solution would be to calculate nums[0] * ... * nums[i - 1] * nums[i + 1] * ... * nums[len(nums) - 1] for every index i individually, giving us a runtime complexity in $\mathcal{O}(n^2)$.

However, we can consider a few facts:

• Let $n$ be an array of $l$ integers. For $i \in \{0, \dotsc, l - 1\}$, let $\mathcal{p_i} = n_0 \times \dotsb \times n_{i - 1}$ be the prefix of $i$, and $\mathcal{s_i} = n_{i + 1} \times \dotsb \times n_{l -1}$ be the suffix of $i$. Then the answer $a_i$ is given by the equation $$a_i = p_i \times s_i.$$ In other words, the answer is given by the product of everything before multiplied by the product of everything afterwards.
• $p_i$ is dependent on the value of $p_{i - 1}$: $$p_i = (n_0 \times \dotsb \times n_{i - 2}) \times n_{i - 1} = p_{i - 1} \times n_{i - 1}$$ except for $p_0 = 1$ since there is no prefix for $a_0$.
• $s_{i - 1}$ is dependent on the value of $s_i$: $$s_{i - 1} = n_{i} \times (n_{i + 1} \times \dotsb \times n_{l - 1}) = n_{i} \times s_{i}$$ except for $s_{l - 1} = 1$ since there is no suffix for $a_{l - 1}$.

We can therefore use the recurrence relations of $p_i$ and $s_i$ to calculate the prefixes and the suffixes through a forward pass and a backward pass respectively.

PRODUCT-EXCEPT-SELF(nums: int array):
	initialise result array with 1s
	
	// calculate prefixes and store them in the array
	prefix = 1
	for i = 0, ..., l - 1:
		result[i] = prefix
		prefix = prefix * nums[i]
	// calculate suffixes and obtain answer
	suffix = 1
	for i = l - 1, ..., 0:
		result[i] = result[i] * suffix  // result = prefix[i] * suffix[i]
		suffix = nums[i] * suffix
	
	return result array

Notice that we can store the prefixes in the array itself to save space, since that doesn’t affect the calculation of the suffixes—that only depends on the previous suffix, and nums!

def productExceptSelf(self, nums: List[int]) -> List[int]:
	res = [1] * (len(nums))
	
	prefix = 1
	for i in range(len(nums)):
		res[i] = prefix
		prefix *= nums[i]
	suffix = 1
	for i in range(len(nums) - 1, -1, -1):
		res[i] *= suffix
		suffix *= nums[i]
	
	return res

Time Complexity

We have two for loops in the algorithm: the forward pass to calculate prefixes, and the backward pass to calculate the suffixes and the answer. Each iteration of both are constant, since it is only two multiplication operations. Therefore, the runtime complexity is in $\mathcal{O}(n)$.

Space Complexity

We don’t count the output array in space complexity analysis. The other variables used are constant, since we only store the latest prefix/suffix—thus, the space complexity is constant, in $\mathcal{O}(1)$.