238. Product of Array Except Self
Problem Description
The problem provided relates to an array transformation challenge. Specifically, you are given an integer array named nums
and the task is to generate a new array named answer
. For each index i
in the new array, answer[i]
should be the product of all the elements in nums
except for nums[i]
. For example, if nums = [1, 2, 3, 4]
, then answer = [24, 12, 8, 6]
because:
answer[0]
should be2*3*4 = 24
answer[1]
should be1*3*4 = 12
answer[2]
should be1*2*4 = 8
answer[3]
should be1*2*3 = 6
Important constraints to note in this problem include:
- The resultant product of any index will fit within a 32-bit integer, meaning we won't have integer overflow issues for the given range of input.
- The desired algorithm should run with a time complexity of O(n), which implies a solution should be achievable in a single pass through the array.
- The division operation cannot be used, which would have been the straightforward approach (multiplying all elements and then dividing by each
nums[i]
for eachanswer[i]
).
These constraints guide us to find a more creative solution that involves using multiplication only and finding a way to accumulate and distribute the products without dividing.
Intuition
The solution to this problem involves accumulating products from both ends of the array. Since we can't use division, we need to think about how we can get the product of all elements except for the current one. A smart way to do this is by multiplying two separate products: one accumulated from the beginning of the array up to the element right before the current one, and another from the end of the array to the element right after the current one.
To elaborate:
-
We initialize two variables,
left
andright
, to 1. They will hold the products of elements to the left and right of the current element, respectively. -
We create an array
ans
to store our results, starting with default values (often zeroes). -
We traverse the array from the left; each
ans[i]
gets the current product on its left (initialized with 1 for the first element as there are no elements to its left), then we updateleft
to includenums[i]
. So during this pass,left
accumulates the product of all numbers to the left of the current index. -
Next, we traverse the array from the right; we multiply each
ans[i]
with the current product on its right (again, starting with 1), and after the multiplication, we updateright
to includenums[i]
. During this pass,right
accumulates the product of all numbers to the right of the current index. -
By the end of these two passes, each
ans[i]
will have been multiplied by both the products of the numbers to its left and right, effectively giving us the product of all other numbers except fornums[i]
.
This approach cleverly bypasses the need for division and adheres to the time complexity requirement since we are only making two passes over the array.
Learn more about Prefix Sum patterns.
Solution Approach
The implementation of the solution leverages a single-dimensional array for storage and two variables for the accumulation of products. The algorithm does not use complex data structures or patterns; instead, it builds on the simple principle of accumulation and iteration over the input array.
Here's a step-by-step breakdown:
-
Initialize an array
ans
to hold our results, filled with zeros, and ensuring that it has the same length as the input arraynums
. -
Two variables,
left
andright
, are initialized to 1 to hold the running product of the elements to the left and right of the current element. -
The first loop iterates over the elements of
nums
from left to right. For each element at indexi
, we setans[i]
to the current value ofleft
sinceleft
contains the product of all elements beforenums[i]
. Then, we updateleft
by multiplying it withnums[i]
, effectively accumulating the product up to the current element.This first loop is described by the following code snippet:
for i, x in enumerate(nums): ans[i] = left left *= x
-
The second loop iterates over the elements of
nums
from right to left. We've already captured the products on the left side in the first pass. Now, for each element at indexi
, we multiply the current value inans[i]
(the left product) withright
, which now represents the product of elements afternums[i]
. Subsequently, we updateright
by multiplying it withnums[i]
, accumulating the product from the end of the array towards the beginning.The second loop corresponds to the following code snippet:
for i in range(n - 1, -1, -1): ans[i] *= right right *= nums[i]
By maintaining two pointers that accumulate the product of elements to the left and right of the current index, and by updating our result array in-place, we manage to get the desired products without ever using division. Moreover, we meet the complexity constraints by maintaining a linear time complexity O(n)
as we traverse the input array exactly twice, no matter its size.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the array nums = [2, 3, 4, 5]
.
Step-by-Step Walkthrough
-
Initialization:
- Initialize the
ans
array with the same length asnums
, in this case,ans = [0, 0, 0, 0]
for storing the results. - Initialize variables
left
andright
with the value 1 to accumulate products from the left and right respectively.
- Initialize the
-
First Pass (Left to Right):
- Iterate over
nums
from left to right, and calculate the left product excluding the current element.
Iteration details:
i = 0
:ans[0]
=left
(which is 1 initially).- Update
left
toleft * nums[0]
, nowleft
= 2. ans
now becomes[1, 0, 0, 0]
.
i = 1
:ans[1]
=left
(which is 2 now).- Update
left
toleft * nums[1]
, nowleft
= 6. ans
is updated to[1, 2, 0, 0]
.
i = 2
:ans[2]
=left
(which is 6).- Update
left
toleft * nums[2]
, nowleft
= 24. - So,
ans
becomes[1, 2, 6, 0]
.
i = 3
:ans[3]
=left
(which is 24).left
is no longer updated since it's the last element.- Final
ans
after the first pass:[1, 2, 6, 24]
.
- Iterate over
-
Second Pass (Right to Left):
- Iterate over
nums
from right to left, and calculate the right product excluding the current element.
Iteration details:
i = 3
:ans[3]
is multiplied byright
(1 initially), soans[3]
remains 24.- Update
right
toright * nums[3]
, nowright
= 5.
i = 2
:ans[2]
=ans[2] * right
(6 * 5), soans[2]
becomes 30.- Update
right
toright * nums[2]
, nowright
= 20.
i = 1
:ans[1]
=ans[1] * right
(2 * 20), thusans[1]
becomes 40.- Update
right
toright * nums[1]
, which makesright
= 60.
i = 0
:ans[0]
=ans[0] * right
(1 * 60), resulting inans[0]
being 60.right
update is not needed since it's the final element.
- Iterate over
-
Final Result:
- The resulting
ans
array after both passes reflects the products of all elements for each position excluding the element itself:ans = [60, 40, 30, 24]
. - This matches what we expect as:
ans[0]
= 3 * 4 * 5 = 60ans[1]
= 2 * 4 * 5 = 40ans[2]
= 2 * 3 * 5 = 30ans[3]
= 2 * 3 * 4 = 24
- The resulting
This walkthrough indicates how the solution approach effectively computes the desired output without the need for division, and it successfully avoids any overflow issues within a 32-bit signed integer range. The time complexity of the solution is O(n)
, as it passes through the array twice regardless of its size.
Solution Implementation
1from typing import List
2
3class Solution:
4 def productExceptSelf(self, nums: List[int]) -> List[int]:
5 # Determine the length of the input list 'nums'.
6 num_length = len(nums)
7
8 # Initialize the answer list with 1's of the same length as 'nums'.
9 answer = [1] * num_length
10
11 # 'left' will represent the cumulative product of elements to the left of the current element.
12 left = 1
13 for i in range(num_length):
14 # Store the cumulative product in the 'answer' list at the current index 'i'.
15 answer[i] = left
16 # Update 'left' to include the product of the current element.
17 left *= nums[i]
18
19 # 'right' will represent the cumulative product of elements to the right of the current element.
20 right = 1
21 for i in range(num_length - 1, -1, -1):
22 # Multiply the existing value in 'answer' by the 'right' value which is the product of elements to the right of 'i'.
23 answer[i] *= right
24 # Update 'right' to include the product of the current element.
25 right *= nums[i]
26
27 # Return the 'answer' list which now contains the products except self.
28 return answer
29
1class Solution {
2 // Method to calculate the product of elements except self
3 public int[] productExceptSelf(int[] nums) {
4 // Get the length of the input array
5 int length = nums.length;
6 // Initialize the answer array with the same length
7 int[] result = new int[length];
8
9 // Initialize 'leftProduct' to 1, to represent the product of elements to the left of the current index
10 int leftProduct = 1;
11 // Loop through the array from left to right
12 for (int i = 0; i < length; i++) {
13 // Set the current element in the result array to 'leftProduct'
14 result[i] = leftProduct;
15 // Multiply 'leftProduct' by the current element in nums for the next iteration (prefix product)
16 leftProduct *= nums[i];
17 }
18
19 // Initialize 'rightProduct' to 1, to represent the product of elements to the right of the current index
20 int rightProduct = 1;
21 // Loop through the array from right to left
22 for (int i = length - 1; i >= 0; i--) {
23 // Multiply the current element in the result array by 'rightProduct'
24 result[i] *= rightProduct;
25 // Multiply 'rightProduct' by the current element in nums for the next iteration (suffix product)
26 rightProduct *= nums[i];
27 }
28
29 // Return the final product except self array
30 return result;
31 }
32}
33
1class Solution {
2public:
3 vector<int> productExceptSelf(vector<int>& nums) {
4 int size = nums.size(); // Store the size of the input vector
5 vector<int> output(size); // Initialize the output vector with the same size as the input
6
7 // Initialize the left running product as 1
8 int leftProduct = 1;
9 // Calculate the running product from the left for each element
10 for (int index = 0; index < size; ++index) {
11 output[index] = leftProduct; // Set the current output element as the product so far from the left
12 leftProduct *= nums[index]; // Update the leftProduct to include the current number
13 }
14
15 // Initialize the right running product as 1
16 int rightProduct = 1;
17 // Calculate the running product from the right for each element
18 for (int index = size - 1; index >= 0; --index) {
19 output[index] *= rightProduct; // Multiply the current output element by the product so far from the right
20 rightProduct *= nums[index]; // Update the rightProduct to include the current number
21 }
22
23 return output; // Return the final output vector containing the product of all elements except self for each position
24 }
25};
26
1function productExceptSelf(nums: number[]): number[] {
2 const length = nums.length; // Total number of elements in input array
3 const result: number[] = new Array(length); // Initialize an array to store the result
4
5 // Forward pass: Calculate the product of all elements to the left of each index
6 for (let i = 0, productToLeft = 1; i < length; i++) {
7 result[i] = productToLeft; // Set the product (initially 1)
8 productToLeft *= nums[i]; // Update the productToLeft for the next index
9 }
10
11 // Backward pass: Calculate the product of all elements to the right of each index
12 for (let i = length - 1, productToRight = 1; i >= 0; i--) {
13 result[i] *= productToRight; // Multiply with the already stored product to the left
14 productToRight *= nums[i]; // Update the productToRight for the previous index
15 }
16
17 return result; // Return the final result array
18}
19
Time and Space Complexity
The time complexity of the code is O(n)
because there are two separate for-loops that each run through the list of n
elements exactly once. The first loop calculates the product of all elements to the left of the current element, and the second loop calculates the product of all elements to the right. Since each loop operates independently and sequentially, the procedures do not multiply in complexity but rather add, resulting in 2n
, which simplifies to O(n)
.
The space complexity is O(1)
, excluding the output array ans
. This is because the algorithm uses a constant number of extra variables (left
, right
, i
, x
). The space taken by these variables does not scale with the size of the input array nums
, hence constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!