Leetcode 238. Product of Array Except Self

Problem Explanation:

Given an array of integers, this problem asks to return a new array where each element is the product of all elements of the original array except the element at the same index. For example, if the input array [1, 2, 3, 4], each element in the output array is calculated as follows:

• For the first element, we multiply all elements [2, 3, 4] and get 24.
• For the second element, we multiply all elements [1, 3, 4] and get 12.
• For the third element, we multiply all elements [1, 2, 4] and get 8.
• For the fourth element, we multiply all elements [1, 2, 3] and get 6.

So the output is [24,12,8,6].

Solution Approach:

The basic idea of the solution is to generate prefix and suffix products for each element in the given array. Prefix products are generated by multiplying all elements to the left of the current index, and suffix products are generated by multiplying all elements to the right of the current index.

For example, let's take the input array to be [1,2,3,4].

• The prefix products are [1, 1, 2, 6] , where prefix[i] = prefix[i-1] * nums[i-1]
• The suffix products are [24, 12, 4, 1], where suffix[i] = suffix[i+1] * nums[i+1]

At each index, if we multiply the prefix and suffix products, we get the desired output which is [24,12,8,6].

The time complexity of this approach is O(n) as we are just iterating through the input array.

A constant space solution is also possible by using the output array to calculate the prefix products and a variable to calculate the suffix products.

Python Solution

1
2python
3class Solution:
4    def productExceptSelf(self, nums):
5        n = len(nums)
6        output = [1]*n
7        
8        # Calculate prefix products
9        for i in range(1, n):
10            output[i] = output[i-1] * nums[i-1]
11            
12        r = 1  # Variable to hold suffix products
13        for i in reversed(range(n)):
14            # For each integer, multiply the product of all numbers to the left and to the right
15            output[i] *= r
16            r *= nums[i]
17        return output

Java Solution

1
2java
3class Solution {
4  public int[] productExceptSelf(int[] nums) {
5    int n = nums.length;
6    int[] output = new int[n];
7    // Calculate prefix products
8    for (int i = 0; i < n; i++)
9      output[i] = i > 0 ? output[i - 1] * nums[i - 1] : 1;
10
11    int r = 1;
12    for (int i = n - 1; i >= 0; i--) {
13      output[i] *= r;
14      r *= nums[i];
15    }
16    return output;
17  }
18}

JavaScript Solution

1
2javascript
3class Solution {
4  productExceptSelf(nums) {
5    const n = nums.length;
6    const output = Array(n).fill(1);
7
8    // Calculate prefix products
9    for (let i = 1; i < n; ++i) {
10      output[i] = output[i - 1] * nums[i - 1];
11    }
12
13    let r = 1;
14
15    for (let i = n - 1; i >= 0; --i) {
16      output[i] *= r;
17      r *= nums[i];
18    }
19
20    return output;
21  }
22}

C++ Solution

1
2cpp
3class Solution {
4 public:
5  vector<int> productExceptSelf(vector<int>& nums) {
6    int n = nums.size();
7    vector<int> output(n, 1);
8
9    // Calculate prefix products
10    for (int i = 1; i < n; i++) 
11      output[i] = output[i - 1] * nums[i - 1];
12    
13    int r = 1;  // holds the suffix products
14
15    // Calculate suffix products
16    for (int i = n - 1; i >= 0; i--) {
17      output[i] *= r;
18      r *= nums[i];
19    }
20    return output;
21  }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int[] ProductExceptSelf(int[] nums) {
5        int n = nums.Length;
6        int[] output = new int[n];
7
8        // Calculate prefix products
9        for (int i = 0; i<n; i++)
10            output[i] = i > 0 ? output[i-1] * nums[i-1] : 1;
11
12        int r = 1;  // holds the suffix products
13
14         // Calculate suffix products
15        for (int i=n-1; i>=0; i--){
16            output[i] *= r;
17            r *= nums[i];
18        }
19
20        return output;
21    }
22}

Swift Solution

1
2swift
3class Solution {
4    func productExceptSelf(_ nums: [Int]) -> [Int] {
5        let n = nums.count
6        var output = Array(repeating: 1, count: n)
7
8        // Calculate prefix products
9        for i in 1..<n {
10            output[i] = output[i - 1] * nums[i - 1]
11        }
12        
13        var r = 1  // Variable to hold suffix products
14        for i in (0..<n).reversed() {
15            // For each integer, multiply the product of all numbers to the left and to the right
16            output[i] *= r
17            r *= nums[i]
18        }
19        return output
20    }
21}

Rust Solution

1
2rust
3impl Solution {
4    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
5        let n = nums.len();
6        let mut output = vec![1; n];
7        
8        // Calculate prefix products
9        for i in 1..n {
10            output[i] = output[i - 1] * nums[i - 1];
11        }
12        
13        let mut r = 1;  // Variable to hold suffix products
14
15        // Calculate suffix products
16        for i in (0..n).rev() {
17            output[i] *= r;
18            r *= nums[i];
19        }
20        
21        output
22    }
23}

TypeScript Solution

1
2Typescript 
3class Solution {
4    productExceptSelf(nums: number[]): number[] {
5        let n = nums.length;
6        let output = Array(n).fill(1);
7
8        // Calculate prefix products
9        for (let i = 1; i < n; i++) {
10            output[i] = output[i - 1] * nums[i - 1];
11        }
12
13        let r = 1; // Variable for holding suffix products
14
15        // Calculate suffix products
16        for (let i = n - 1; i >= 0; i--) {
17            output[i] *= r;
18            r *= nums[i];
19        }
20
21        return output;
22    }
23}

The above are the various implementations of the efficient solution to the problem in different programming languages to fit into your context.