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 get24
. - For the second element, we multiply all elements
[1, 3, 4]
and get12
. - For the third element, we multiply all elements
[1, 2, 4]
and get8
. - For the fourth element, we multiply all elements
[1, 2, 3]
and get6
.
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.
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.