Product of Array Except Self
Problem 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
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation: The integer at the 0th index of the output array is the multiplication of 2x3x4 (except of 1) . The integer at the 1st index is the multiplication of 1x3x4 (except of 2) and so on.
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Explanation: In the output array ,the integer at 0th index of the output is the multiplication of 1 x 0 x (-3) x 3=0. (except of -11) .
The integer at the 2nd index is the multiplication of (-1)x(1)x(-3)x(3)=9 (except of 0) and so on.
Constraints:
- 2 <= nums.length <= 10^5
- -30 <= nums[i] <= 30
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
We will be analysing the solution with the brute force approach and prefix sum. Each approach has its own benefits and challenges regarding how fast it works and how much memory it uses.
Brute Force Approach
Intuition
Since, we are asked to output the resultant array where each integer of the resultant array is the multiplication of all the integers except itself in the nums array.
The first approach which comes to our mind is, to pick one element and multiply it with the remaining elements except the number itself and then store the multiplied value in the answer array.
Approach
Initialization:
- The method productExceptSelf takes an integer array nums as input.
It initializes an array answer of the same size as nums to store the result.
Nested Loops:
- Outer loop (i): Iterates over each element of nums and calculates the product of all other elements except nums[i].
- Inner loop (j): Computes the product of all elements except the one at index i.
If i != j, include nums[j] in the product.
Store the Result:
After calculating the product for the i-th element, store it in answer[i].
Return Result:
Once all elements are processed, return the answer array.
Dry-Run
Input: nums = [3,5,6,4]
Output: [120, 72, 60, 90]
Initial Setup:
nums = [3, 5, 6, 4]
ans = [0, 0, 0, 0] (Initialized to store the results)
Outer Loop Iteration (i = 0):
We want to calculate the product of all elements except nums[0] = 3.
prod = 1 (Initial product for this iteration)
Inner Loop:
j = 0: i==j (both indices are equal). Skip.
j = 1: prod *= nums[1] = 5 → prod = 1 * 5 = 5.
j = 2: prod *= nums[2] = 6 → prod = 5 * 6 = 30.
j = 3: prod *= nums[3] = 4 → prod = 30 * 4 = 120.
Result after i = 0: ans[0] = 120.
Outer Loop Iteration (i = 1):
We want to calculate the product of all elements except nums[1] = 5.
prod = 1 (Reset product for this iteration)
Inner Loop:
j = 0: prod *= nums[0] = 3 → prod = 1 * 3 = 3.
j = 1: i==j (both indices are equal). Skip.
j = 2: prod *= nums[2] = 6 → prod = 3 * 6 = 18.
j = 3: prod *= nums[3] = 4 → prod = 18 * 4 = 72.
Result after i = 1: ans[1] = 72.
Outer Loop Iteration (i = 2):
We want to calculate the product of all elements except nums[2] = 6.
prod = 1 (Reset product for this iteration)
Inner Loop:
j = 0: prod *= nums[0] = 3 → prod = 1 * 3 = 3.
j = 1: prod *= nums[1] = 5 → prod = 3 * 5 = 15.
j = 2: i==j (both indices are equal). Skip.
j = 3: prod *= nums[3] = 4 → prod = 15 * 4 = 60.
Result after i = 2: ans[2] = 60.
Outer Loop Iteration (i = 3):
We want to calculate the product of all elements except nums[3] = 4.
prod = 1 (Reset product for this iteration)
Inner Loop:
j = 0: prod *= nums[0] = 3 → prod = 1 * 3 = 3.
j = 1: prod *= nums[1] = 5 → prod = 3 * 5 = 15.
j = 2: prod *= nums[2] = 6 → prod = 15 * 6 = 90.
j = 3: i==j (both indices are equal). Skip.
Result after i = 3: ans[3] = 90.
Final Result:
The output array ans after completing all iterations is: ans=[120,72,60,90].
Summary of ans:
- ans[0] = 5 * 6 * 4 = 120
- ans[1] = 3 * 6 * 4 = 72
- ans[2] = 3 * 5 * 4 = 60
- ans[3] = 3 * 5 * 6 = 90
Brute Force Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// Get the size of the input array
int n = nums.size();
// Initialize the answer array with 1s.
// This will hold the product of all elements except the current index.
vector<int> answer(n, 1);
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// Initialize the product variable to calculate the product of elements
// excluding the current index
int product = 1;
// Iterate through the array to calculate the product of elements
// excluding the current index
for (int j = 0; j < n; j++) {
// Skip the current index
if (i != j) {
// Multiply the current element to the product
product *= nums[j];
}
}
// Assign the calculated product to the current index in the answer array
answer[i] = product;
}
// Return the answer array
return answer;
}
};
2. Java Try on Compiler
class Solution {
public int[] productExceptSelf(int[] nums) {
// Get the length of the input array
int n = nums.length;
// Initialize the answer array to hold the product of all elements
// except the one at the current index
int[] answer = new int[n];
// Iterate through each index in the array
for (int i = 0; i < n; i++) {
// Initialize the product variable to calculate the product of elements
// excluding the current index
int product = 1;
// Iterate through the array to compute the product of all elements
// except the current index
for (int j = 0; j < n; j++) {
// Skip the current index
if (i != j) {
// Multiply the current element to the product
product *= nums[j];
}
}
// Assign the calculated product to the current index in the answer array
answer[i] = product;
}
// Return the answer array
return answer;
}
}
3. Python Try on Compiler
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# Get the length of the input array
n = len(nums)
# Initialize the answer array with 1s
# This array will hold the product of all elements except the one at the current index
answer = [1] * n
# Iterate through each index in the array
for i in range(n):
# Initialize the product variable to calculate the product of elements
# excluding the current index
product = 1
# Iterate through the array to compute the product of all elements
# except the current index
for j in range(n):
# Skip the current index
if i != j:
# Multiply the current element to the product
product *= nums[j]
# Assign the calculated product to the current index in the answer array
answer[i] = product
# Return the answer array
return answer
4. JavaScript Try on Compiler
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
// Get the length of the input array
let n = nums.length;
// Initialize the answer array with 1s
// This array will store the product of all elements except the current index
let answer = new Array(n).fill(1);
// Iterate through each index in the array
for (let i = 0; i < n; i++) {
// Initialize the product variable to calculate the product of elements
// excluding the current index
let product = 1;
// Iterate through the array to compute the product of all elements
// except the current index
for (let j = 0; j < n; j++) {
// Skip the current index
if (i !== j) {
// Multiply the current element to the product
product *= nums[j];
}
}
// Assign the calculated product to the current index in the answer array
answer[i] = product;
}
// Return the answer array
return answer;
};
Time Complexity: O(n^2)
The productExceptSelf method has a nested loop structure where:
- The outer loop runs n times, where n is the length of the input array nums.
- The inner loop also runs n times for each iteration of the outer loop.
Thus, the time complexity of the productExceptSelf method is O(n^2) because, for each element i in the array, you are iterating through all other elements to calculate the product (except for i itself).
Therefore, the time complexity of the entire solution is: O(n^2) for the productExceptSelf method.
Space Complexity: O(n)
Auxiliary Space Complexity
The auxiliary space refers to any extra space used by the algorithm, excluding the input and output space.
In the productExceptSelf method, an additional array answer[] is created to store the result, which has the same size as the input array nums. Therefore, the auxiliary space required by the method is O(n), as it only uses extra space for the answer array.
So, the auxiliary space complexity is: O(n) due to the extra answer array.
Total Space Complexity
The total space complexity is the sum of the space used for the input and output:
- O(n) for the input array nums.
- O(n) for the output array answer[].
So, the overall space complexity is:O(n) + O(n) = O(n).
Reviewing the constraints for the given question which is "2 <= nums.length <= 10^5" will result in Time Limit Exceeded for the Brute Force Approach.
The interviewer will be unhappy with the approach, we need to figure out an optimal solution.
Optimal Approach
Intuition
Before moving to the optimal approach,
We saw that for each element, we are redoing the multiplication for every other element.
If n is large, this leads to a lot of repeated work, which makes the solution slow.
If we consider the product of all elements in the array, let's call it totalProduct:
The product of all elements except nums[i] can be computed as: product except nums[i]=totalProduct/nums[i] . But it may result in runtime error if nums[i] is 0 because division with 0 is not possible.
But the problem specifies that we cannot use division. So, we need a different way to achieve the same result.
In order to optimize it further, we need to avoid the repeated work. But how ??
Can we break the problem into two parts?
Left Product and the Right Product for each element. Why ??
Let's see how to proceed.
Left Product (for each element)
- For each element i, we can calculate the product of all elements to the left of i (i.e., all elements before i in the array).
- The left product for any element i is the product of all elements before the element i in the array.
- For example, if the array is [a, b, c, d]:
- The left product for a is 1 (since there's no element before it).
- The left product for b is a (product of elements before b).
- The left product for c is a * b (product of elements before c).
- The left product for d is a * b * c (product of elements before d).
- For example, if the array is [a, b, c, d]:
So, if we know the left product for each element, we can start building the output array.
Right Product (for each element)
- Similarly, we can calculate the product of all elements to the right of i (i.e., all elements after i in the array).
- Using the same example [a, b, c, d]:
- The right product for a is b * c * d.
- The right product for b is c * d.
- The right product for c is d.
- The right product for d is 1 (since there are no elements after d).
By combining the left and right products, we can calculate the final result in just O(n) time.
How do we combine ?
For any element i, the final product (ignoring nums[i]) can be calculated by multiplying its left product and right product: output[i]=leftProduct[i]×rightProduct[i]
Where:
- leftProduct[i] gives us the product of all elements before i in the array.
- rightProduct[i] gives us the product of all elements after i in the array.
Thus, the final array output[] can be filled efficiently by combining these two "partial products".
But, we need a O(1) extra space complexity other than the output array. But aren't we consuming two arrays i.e the leftProduct[] and the rightProduct[] which will result in O(n)+O(n)=O(2n)= O(n) extra space complexity?
We can save the extra space by using a variable "suffix" which will be responsible to store the product of numbers encountered when we traverse the array from the end.
In simple words,
The leftProduct is calculated during the left-to-right pass, and we use the "suffix" variable in the right-to-left pass.
In this way, we figured out the auxiliary space complexity to be O(1).
We just figured out an optimal approach and the technique we use is called the prefix sum approach. So, let's name the leftProduct[] array as the prefix[] array as it will store the product of all the numbers encountered before a given number.
Approach
Initialization (prefix[0] = nums[0]):The first element of sufArray is just the first element of nums because there's no element before it in the array (it's the "left product" of the first element).
Left Product Pass:We go through the array from left to right, filling up prefix. Each element in prefix[i] will contain the product of all elements from nums[0] to nums[i-1].
Right Product Pass:We then go through the array from right to left, using a suffix variable to store the product of all elements to the right of each element.
For each i, we multiply the value in prefix[i] by suffix, which gives the final product of all elements except nums[i].
Final Adjustment for prefix[0]:The first element in the array is updated after the right product pass with the final suffix value.
Dry-Run
Input: nums = [3,5,6,4]
Output: [120, 72, 60, 90]
Initialization:
- len = 4 (length of the input array nums)
- prefix = [0, 0, 0, 0] (initial result array, which will hold the product except self)
First Pass (Left Pass: Calculating Prefix Product):
We initialize the prefix[0] = nums[0] = 3.
Then, we calculate the prefix product for the rest of the array:
- i = 1:
prefix[1] = prefix[0] * nums[1] = 3 * 5 = 15
prefix = [3, 15, 0, 0] - i = 2:
prefix[2] = prefix[1] * nums[2] = 15 * 6 = 90
prefix = [3, 15, 90, 0] - i = 3:
prefix[3] = prefix[2] * nums[3] = 90 * 4 = 360
prefix = [3, 15, 90, 360]
Second Pass (Right Pass: Calculating Suffix Product):
We initialize the suffix = 1.
Now we iterate from right to left (starting from i = 3 down to i = 1):
- i = 3:
prefix[3] = prefix[2] * suffix = 90 * 1 = 90
suffix = suffix * nums[3] = 1 * 4 = 4
prefix = [3, 15, 90, 90] - i = 2:
prefix[2] = prefix[1] * suffix = 15 * 4 = 60
suffix = suffix * nums[2] = 4 * 6 = 24
prefix = [3, 15, 60, 90] - i = 1:
prefix[1] = prefix[0] * suffix = 3 * 24 = 72
suffix = suffix * nums[1] = 24 * 5 = 120
prefix = [3, 72, 60, 90]
Final Step (Leftmost Element):
After completing the right pass, we update prefix[0] with the suffix value:
- prefix[0] = suffix = 120
- prefix = [120, 72, 60, 90]
Final Output:
After completing both passes, the final prefix array, which contains the product of all elements except the element at that index, is:
[120, 72, 60, 90]
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
// Array to store the result (product except self)
vector<int> prefix(len);
// First element is just nums[0] because there's no element before it.
prefix[0] = nums[0];
// Left Pass: Calculate the prefix product for each element
for (int i = 1; i < len; i++) {
prefix[i] = prefix[i - 1] * nums[i];
}
// Right Pass: Calculate the suffix product for each element
// This stores the product of elements to the right of the current element.
int suffix = 1;
for (int i = len - 1; i > 0; i--) {
// Multiply with the suffix product so far
prefix[i] = prefix[i - 1] * suffix;
// Update the suffix product for the next element
suffix *= nums[i];
}
// Finally, the leftmost element gets the suffix product
prefix[0] = suffix;
return prefix;
}
};2. Java Try on Compiler
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
// Array to store the result (product except self)
int prefix[] = new int[len];
// First element is just nums[0] because there's no element before it.
prefix[0] = nums[0];
// Left Pass: Calculate the prefix product for each element
for (int i = 1; i < len; i++) {
prefix[i] = prefix[i - 1] * nums[i];
}
// Right Pass: Calculate the suffix product for each element
// This stores the product of elements to the right of the current element.
int suffix = 1;
for (int i = len - 1; i > 0; i--) {
// Multiply with the suffix product so far
prefix[i] = prefix[i - 1] * suffix;
// Update the suffix product for the next element
suffix *= nums[i];
}
// Finally, the leftmost element gets the suffix product
prefix[0] = suffix;
// Return the result array
return prefix;
}
}3. Python Try on Compiler
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# Get the length of the input array
length = len(nums)
# Array to store the result (product except self)
prefix = [0] * length
# First element is just nums[0] because there's no element before it.
prefix[0] = nums[0]
# Left Pass: Calculate the prefix product for each element
for i in range(1, length):
prefix[i] = prefix[i - 1] * nums[i]
# Right Pass: Calculate the suffix product for each element
# This stores the product of elements to the right of the current element.
suffix = 1
for i in range(length - 1, 0, -1):
# Multiply with the suffix product so far
prefix[i] = prefix[i - 1] * suffix
# Update the suffix product for the next element
suffix *= nums[i]
# Finally, the leftmost element gets the suffix product
prefix[0] = suffix
# Return the result array
return prefix 4. JavaScript Try on Compiler
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
let len = nums.length;
// Array to store the result (product except self)
let prefix = new Array(len);
// First element is just nums[0] because there's no element before it.
prefix[0] = nums[0];
// Left Pass: Calculate the prefix product for each element
for (let i = 1; i < len; i++) {
prefix[i] = prefix[i - 1] * nums[i];
}
// Right Pass: Calculate the suffix product for each element
// This stores the product of elements to the right of the current element.
let suffix = 1;
for (let i = len - 1; i > 0; i--) {
// Multiply with the suffix product so far
prefix[i] = prefix[i - 1] * suffix;
// Update the suffix product for the next element
suffix *= nums[i];
}
// Finally, the leftmost element gets the suffix product
prefix[0] = suffix;
// Return the result array
return prefix;
};Time Complexity: O(n)
The algorithm consists of two main passes through the array:
Left Pass (Prefix Product Calculation):
- A single loop runs from i = 1 to len - 1, performing one multiplication per iteration.
- Time Complexity: O(n), where n is the length of the input array nums.
Right Pass (Suffix Product Calculation):
- Another loop runs from i = len - 1 to 1, performing one multiplication per iteration.
- Time Complexity: O(n).
Since both loops run in linear time, the total time complexity is: O(n)+O(n)= O(n)
Space Complexity: O(1)
Auxiliary Space Complexity:
Auxiliary space refers to the extra space used by the algorithm excluding the input and output.
- The algorithm uses a constant variable suffix to store the product of elements to the right of the current element.
- No other auxiliary data structures are used aside from this constant space.
Thus, auxiliary space complexity is: O(1).
Total Space Complexity: O(n)
Input Array contains n elements which results in complexity of O(n).
"suffix" variable accounts for O(1) space.
The Total space complexity is : O(n).
Learning Tip
Given an integer array nums, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Given an integer array nums, find the subarray with the largest sum, and return its sum.