Problem: Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

• You must solve it without using division.
• Your solution should run in O(n) time.
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example 1:

Input:

nums = [1, 2, 3, 4]

Output:

[24, 12, 8, 6]

Explanation:

• answer[0] = 2 * 3 * 4 = 24
• answer[1] = 1 * 3 * 4 = 12
• answer[2] = 1 * 2 * 4 = 8
• answer[3] = 1 * 2 * 3 = 6

Example 2:

Input:

nums = [-1, 1, 0, -3, 3]

Output:

[0, 0, 9, 0, 0]

Explanation:

• answer[0] = 1 * 0 * -3 * 3 = 0
• answer[1] = -1 * 0 * -3 * 3 = 0
• answer[2] = -1 * 1 * -3 * 3 = 9
• answer[3] = -1 * 1 * 0 * 3 = 0
• answer[4] = -1 * 1 * 0 * -3 = 0

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow-up:

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Algorithm Explanation:

The key idea here is to use two passes to compute the product of elements except the current one, avoiding the division operation.

1. First Pass (Left Products):
   • Traverse the array from left to right. For each element nums[i], compute the product of all the elements to its left and store it in output[i].
2. Second Pass (Right Products):
   • Traverse the array from right to left. For each element nums[i], multiply the current value in output[i] by the product of all the elements to its right. This way, we update output[i] to store the product of all elements except nums[i].

Code Implementation:

#include <stdio.h>
#include <stdlib.h>

void productExceptSelf(int* inputArray, int arraySize, int* outputArray) 
{
    int walkLeft = 1, walkRight = 1;

    // First pass: calculate the left products
    for (int i = 0; i < arraySize; i++) {
        outputArray[i] = walkLeft;
        walkLeft *= inputArray[i];
    }

    // Second pass: calculate the right products and update the output array
    for (int i = arraySize - 1; i >= 0; i--) {
        outputArray[i] *= walkRight;
        walkRight *= inputArray[i];
    }
}

int main() 
{
    int inputArray[] = {1, 2, 3, 4};
    int arraySize = sizeof(inputArray) / sizeof(inputArray[0]);
    int outputArray[arraySize];

    productExceptSelf(inputArray, arraySize, outputArray);

    for (int i = 0; i < arraySize; i++) {
        printf("%d ", outputArray[i]);
    }

    return 0;
}

Explanation of the Code:

1. Initialization:

   • walkLeft and walkRight are initialized to 1, used to accumulate the products as we traverse the array from left to right and right to left.

2. First Pass:

   • We fill outputArray with the products of all elements to the left of each index.
   • outputArray[i] = walkLeft stores the left product of the elements.
   • walkLeft *= inputArray[i] updates the product for the next iteration.

3. Second Pass:

   • We multiply the current value of outputArray[i] by walkRight, which accumulates the products of elements to the right of the index.
   • walkRight *= inputArray[i] updates the product for the next iteration.

Time and Space Complexity:

• Time Complexity: O(n)O(n) where nn is the number of elements in the input array. We make two passes over the array.
• Space Complexity: O(1)O(1) extra space, because the output array is the only extra space used, and we’re not using additional space besides it.