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.
1class Solution {
2 public int[] productExceptSelf(int[] nums) {
3 int n = nums.length;
4 int[] left = new int[n];
5 int[] right = new int[n];
6 int[] answer = new int[n];
7 left[0] = 1;
8 right[n-1] = 1;
9 for (int i = 1; i < n; i++)
10 left[i] = nums[i-1] * left[i-1];
11 for (int i = n-2; i >= 0; i--)
12 right[i] = nums[i+1] * right[i+1];
13 for (int i = 0; i < n; i++)
14 answer[i] = left[i] * right[i];
15 return answer;
16 }
17}The implementation in Java uses auxiliary arrays 'left' and 'right'. It fills them with calculated prefix and suffix products and derives the final result by multiplying these respective arrays.
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.
1#include<stdio.h>
2void productExceptSelf(int* nums, int numsSize, int* returnSize) {
3 int right = 1;
4 int answer[numsSize];
5 answer[0] = 1;
6 for (int i = 1; i < numsSize; i++)
7 answer[i] = nums[i - 1] * answer[i - 1];
8 for (int i = numsSize - 1; i >= 0; i--) {
9 answer[i] = answer[i] * right;
10 right *= nums[i];
11 }
12 *returnSize = numsSize;
13 for (int i = 0; i < numsSize; i++)
14 printf("%d ", answer[i]);
15 printf("\n");
16}This C solution reverses the calculation order to incorporate right-side product values while maintaining a single result array.