Sponsored
Sponsored
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.
1#include<stdio.h>
2void productExceptSelf(int* nums, int numsSize, int* returnSize) {
3 int left[numsSize], right[numsSize], answer[numsSize];
4 left[0] = 1;
5 right[numsSize-1] = 1;
6 for (int i = 1; i < numsSize; i++)
7 left[i] = nums[i-1] * left[i-1];
8 for (int i = numsSize-2; i >= 0; i--)
9 right[i] = nums[i+1] * right[i+1];
10 for (int i = 0; i < numsSize; i++)
11 answer[i] = left[i] * right[i];
12 *returnSize = numsSize;
13 for (int i = 0; i < numsSize; i++)
14 printf("%d ", answer[i]);
15 printf("\n");
16}The solution uses two auxiliary arrays for calculating prefixes and suffixes. The algorithm computes these in two separate for-loops and then calculates the result array in one final loop by multiplying appropriate elements of the prefix and suffix 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.
This C solution reverses the calculation order to incorporate right-side product values while maintaining a single result array.