This approach involves calculating two additional arrays:
By multiplying the corresponding prefix and suffix product, we obtain the product of all other elements except the one at that given index.
Time Complexity: O(n) since it involves three passes through the array.
Space Complexity: O(n) due to the two additional arrays used.
1from typing import List
2class Solution:
3 def productExceptSelf(self, nums: List[int]) -> List[int]:
4 n = len(nums)
5 left = [1] * n
6 right = [1] * n
7 answer = [0] * n
8 for i in range(1, n):
9 left[i] = nums[i-1] * left[i-1]
10 for i in range(n-2, -1, -1):
11 right[i] = nums[i+1] * right[i+1]
12 for i in range(n):
13 answer[i] = left[i] * right[i]
14 return answerIn Python, lists 'left' and 'right' are utilized to store prefix and suffix products. Then, by performing a simple calculation for each index, the final array is derived.
This approach optimizes space usage by performing the transformations directly on the output array. It first fills the output array with the left product transformation, then updates it with right products.
With the first pass, it calculates the products of elements to the left, and on the second pass, it adjusts for the products of elements to the right by maintaining a right product multiplier.
Time Complexity: O(n) due to linear pass transformations for left and right products.
Space Complexity: O(1) as no extra arrays are used, except for the output.
1public class Solution {
2 public int[] ProductExceptSelf(int[] nums) {
3 int n = nums.Length;
4 int[] answer = new int[n];
5 answer[0] = 1;
6 for (int i = 1; i < n; i++)
7 answer[i] = answer[i - 1] * nums[i - 1];
8 int right = 1;
9 for (int i = n - 1; i >= 0; i--) {
10 answer[i] *= right;
11 right *= nums[i];
12 }
13 return answer;
14 }
15}The C# implementation makes use of the answer array storing left products, followed by in-situ adjustment with 'right' computations.