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 be 2*3*4 = 24
  • answer[1] should be 1*3*4 = 12
  • answer[2] should be 1*2*4 = 8
  • answer[3] should be 1*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 each answer[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:

  1. We initialize two variables, left and right, to 1. They will hold the products of elements to the left and right of the current element, respectively.

  2. We create an array ans to store our results, starting with default values (often zeroes).

  3. 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 update left to include nums[i]. So during this pass, left accumulates the product of all numbers to the left of the current index.

  4. 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 update right to include nums[i]. During this pass, right accumulates the product of all numbers to the right of the current index.

  5. 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 for nums[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.

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:

  1. Initialize an array ans to hold our results, filled with zeros, and ensuring that it has the same length as the input array nums.

  2. Two variables, left and right, are initialized to 1 to hold the running product of the elements to the left and right of the current element.

  3. The first loop iterates over the elements of nums from left to right. For each element at index i, we set ans[i] to the current value of left since left contains the product of all elements before nums[i]. Then, we update left by multiplying it with nums[i], effectively accumulating the product up to the current element.

    This first loop is described by the following code snippet:

    1for i, x in enumerate(nums):
    2    ans[i] = left
    3    left *= x
  4. 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 index i, we multiply the current value in ans[i] (the left product) with right, which now represents the product of elements after nums[i]. Subsequently, we update right by multiplying it with nums[i], accumulating the product from the end of the array towards the beginning.

    The second loop corresponds to the following code snippet:

    1for i in range(n - 1, -1, -1):
    2    ans[i] *= right
    3    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.

💪
Level Up Your
Algo Skills

Example 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

  1. Initialization:

    • Initialize the ans array with the same length as nums, in this case, ans = [0, 0, 0, 0] for storing the results.
    • Initialize variables left and right with the value 1 to accumulate products from the left and right respectively.
  2. First Pass (Left to Right):

    • Iterate over nums from left to right, and calculate the left product excluding the current element.

    Iteration details:

    1. i = 0:
      • ans[0] = left (which is 1 initially).
      • Update left to left * nums[0], now left = 2.
      • ans now becomes [1, 0, 0, 0].
    2. i = 1:
      • ans[1] = left (which is 2 now).
      • Update left to left * nums[1], now left = 6.
      • ans is updated to [1, 2, 0, 0].
    3. i = 2:
      • ans[2] = left (which is 6).
      • Update left to left * nums[2], now left = 24.
      • So, ans becomes [1, 2, 6, 0].
    4. 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].
  3. Second Pass (Right to Left):

    • Iterate over nums from right to left, and calculate the right product excluding the current element.

    Iteration details:

    1. i = 3:
      • ans[3] is multiplied by right (1 initially), so ans[3] remains 24.
      • Update right to right * nums[3], now right = 5.
    2. i = 2:
      • ans[2] = ans[2] * right (6 * 5), so ans[2] becomes 30.
      • Update right to right * nums[2], now right = 20.
    3. i = 1:
      • ans[1] = ans[1] * right (2 * 20), thus ans[1] becomes 40.
      • Update right to right * nums[1], which makes right = 60.
    4. i = 0:
      • ans[0] = ans[0] * right (1 * 60), resulting in ans[0] being 60.
      • right update is not needed since it's the final element.
  4. 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 = 60
      • ans[1] = 2 * 4 * 5 = 40
      • ans[2] = 2 * 3 * 5 = 30
      • ans[3] = 2 * 3 * 4 = 24

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫