Description
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.
Examples:
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]Solution in Python
Approach:
We can solve this by using two passes through the array:
- First Pass (Left Products): Compute the product of all the elements to the left of each element.
- Second Pass (Right Products): Compute the product of all the elements to the right of each element, while updating the result array with the product of left and right products.
Python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# Step 1: Initialize the result array with 1's
# We will use this array to store the product of all elements except nums[i]
n = len(nums)
result = [1] * n
# Step 2: Calculate the left products for each element
# left_product will store the cumulative product of elements to the left of nums[i]
left_product = 1
for i in range(n):
result[i] = left_product # Store the product of all elements to the left of nums[i]
left_product *= nums[i] # Update left_product to include nums[i] for the next element
# Step 3: Calculate the right products and update the result array
# right_product will store the cumulative product of elements to the right of nums[i]
right_product = 1
for i in range(n - 1, -1, -1): # Iterate from the end of the array
result[i] *= right_product # Multiply with the right product to get the final product
right_product *= nums[i] # Update right_product to include nums[i] for the next element
# Step 4: Return the result array
return resultExplanation:
- Result Array Initialization:
- We initialize the
resultarray with 1’s because multiplying by 1 has no effect on the final product. This array will store the product of all elements exceptnums[i].
- We initialize the
- First Pass – Left Product:
- We maintain a
left_productvariable, which stores the cumulative product of all elements to the left of the current element. - For each element
i, we setresult[i]toleft_product, which gives us the product of all elements to the left ofi. - We then update
left_productby multiplying it withnums[i], so it includes the current element in the next iteration.
- We maintain a
- Second Pass – Right Product:
- We maintain a
right_productvariable, which stores the cumulative product of all elements to the right of the current element. - We iterate the array from right to left (i.e., starting from the last element).
- For each element
i, we multiplyresult[i]byright_product, which gives us the final product of all elements exceptnums[i]. - We then update
right_productby multiplying it withnums[i], so it includes the current element in the next iteration.
- We maintain a
- Final Result:
- The
resultarray will now contain the product of all elements exceptnums[i]for eachi.
- The
Solution in Javascript
JavaScript
var productExceptSelf = function(nums) {
// Step 1: Initialize the result array with 1's
const n = nums.length;
const result = new Array(n).fill(1);
// Step 2: Calculate the left products
let leftProduct = 1; // Initialize the left product as 1
for (let i = 0; i < n; i++) {
result[i] = leftProduct; // Set result[i] to the left product
leftProduct *= nums[i]; // Update leftProduct to include nums[i]
}
// Step 3: Calculate the right products and update the result array
let rightProduct = 1; // Initialize the right product as 1
for (let i = n - 1; i >= 0; i--) { // Traverse from the end to the start
result[i] *= rightProduct; // Multiply the current result by the right product
rightProduct *= nums[i]; // Update rightProduct to include nums[i]
}
// Step 4: Return the final result array
return result;
};Solution in Java
Java
class Solution {
public int[] productExceptSelf(int[] nums) {
// Step 1: Initialize the result array
int n = nums.length;
int[] result = new int[n];
// Step 2: Calculate the left products
int leftProduct = 1; // Initialize the left product as 1
for (int i = 0; i < n; i++) {
result[i] = leftProduct; // Set result[i] to the left product
leftProduct *= nums[i]; // Update leftProduct to include nums[i]
}
// Step 3: Calculate the right products and update the result array
int rightProduct = 1; // Initialize the right product as 1
for (int i = n - 1; i >= 0; i--) { // Traverse from the end to the start
result[i] *= rightProduct; // Multiply the current result by the right product
rightProduct *= nums[i]; // Update rightProduct to include nums[i]
}
// Step 4: Return the final result array
return result;
}
}Solution in C++
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// Step 1: Initialize the result vector
int n = nums.size();
vector<int> result(n, 1); // Create a result vector filled with 1's
// Step 2: Calculate the left products
int leftProduct = 1; // Initialize the left product as 1
for (int i = 0; i < n; i++) {
result[i] = leftProduct; // Set result[i] to the left product
leftProduct *= nums[i]; // Update leftProduct to include nums[i]
}
// Step 3: Calculate the right products and update the result vector
int rightProduct = 1; // Initialize the right product as 1
for (int i = n - 1; i >= 0; i--) { // Traverse from the end to the start
result[i] *= rightProduct; // Multiply the current result by the right product
rightProduct *= nums[i]; // Update rightProduct to include nums[i]
}
// Step 4: Return the final result vector
return result;
}
};