Product of Array Except Self (opens in a new tab) Medium

Problem

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

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

Output: [24,12,8,6]

Summary

To solve this problem, we need to use two passes over the array. In the first pass, the solution calculates the product of all elements to the left of each element in the array, storing each product in the corresponding position in answer. In the second pass, the solution calculates the product of all elements to the right of each element in the array, multiplying it by the corresponding value in answer. The final answer array contains the desired products.

Solution

In TypeScript

function productExceptSelf(nums: number[]): number[] {
	const n = nums.length;
	const answer = new Array(n).fill(1);
	let leftProduct = 1;
	for (let i = 0; i < n; i++) {
		answer[i] *= leftProduct;
		leftProduct *= nums[i];
	}
	let rightProduct = 1;
	for (let i = n - 1; i >= 0; i--) {
		answer[i] *= rightProduct;
		rightProduct *= nums[i];
	}
	return answer;
}

In Python

def productExceptSelf(nums: List[int]) -> List[int]:
	n = len(nums)
	answer = [1] * n
	leftProduct = 1
	for i in range(n):
		answer[i] *= leftProduct
		leftProduct *= nums[i]
	rightProduct = 1
	for i in range(n - 1, -1, -1):
		answer[i] *= rightProduct
		rightProduct *= nums[i]
	return answer

Step-by-step explanation

The length of the input array is stored in a variable n.

const n = nums.length;

An array of length n is created and filled with 1 values. This array will hold the final products for each element of the input array.

const answer = new Array(n).fill(1);

A variable leftProduct is initialized to 1. This variable will hold the product of all elements to the left of the current element.

let leftProduct = 1;

A loop is started that iterates over the input array from left to right:
1. The corresponding element in answer is multiplied by leftProduct.
2. leftProduct is multiplied by the current element in the input array.
3. This calculates the product of all elements to the left of the current element.

for (let i = 0; i < n; i++) {
	answer[i] *= leftProduct;
	leftProduct *= nums[i];
}

A variable rightProduct is initialized to 1. This variable will hold the product of all elements to the right of the current element.

let rightProduct = 1;

A loop is started that iterates over the input array from right to left:
1. The corresponding element in answer is multiplied by rightProduct.
2. rightProduct is multiplied by the current element in the input array.
3. This calculates the product of all elements to the right of the current element.

for (let i = n - 1; i >= 0; i--) {
	answer[i] *= rightProduct;
	rightProduct *= nums[i];
}

The function returns the answer array, which contains the desired products.

return answer;

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n) because the solution uses two separate passes over the array.

Space Complexity

The space complexity of this solution is O(n) because the answer array is created to hold the final products.

Variations

Prefix and Suffix Products

As demonstrated in the solution above, we calculate the prefix and suffix products of each element in the input array nums, and then multiply the prefix and suffix products to get the final result. This approach has a time complexity of O(n) and a space complexity of O(n).

Two Pointers

We can use two pointers to maintain the prefix and suffix products of each element in the input array nums. This approach has a time complexity of O(n) and a space complexity of O(1).

In TypeScript

function productExceptSelf(nums: number[]): number[] {
		const n = nums.length;
		const result = new Array<number>(n);
		let leftProduct = 1;
		let rightProduct = 1;
		for (let i = 0; i < n; i++) {
				result[i] = leftProduct;
				leftProduct *= nums[i];
		}
		for (let i = n - 1; i >= 0; i--) {
				result[i] *= rightProduct;
				rightProduct *= nums[i];
		}
		return result;
}

In Python

def productExceptSelf(nums: List[int]) -> List[int]:
		n = len(nums)
		result = [1] * n
		leftProduct = 1
		rightProduct = 1
		for i in range(n):
				result[i] *= leftProduct
				leftProduct *= nums[i]
		for i in range(n - 1, -1, -1):
				result[i] *= rightProduct
				rightProduct *= nums[i]
		return result

Division

We can calculate the product of all elements in the input array nums, and then divide the product by each element to get the final result. This approach has a time complexity of O(n) and a space complexity of O(1), but it may not work if there are zero elements in the input array.

In TypeScript

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const product = nums.reduce((acc, val) => acc * val);
    const result = new Array<number>(n);
    for (let i = 0; i < n; i++) {
        result[i] = product / nums[i];
    }
    return result;
}

In Python

def productExceptSelf(nums: List[int]) -> List[int]:
    product = 1
    zero_count = 0
    for num in nums:
        if num == 0:
            zero_count += 1
            if zero_count > 1:
                return [0] * len(nums)
        else:
            product *= num
    if zero_count == 1:
        return [0 if num != 0 else product for num in nums]
    else:
        return [product // num for num in nums]

4. 3Sum 6. Combination Sum