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]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

Test Cases

Example 1: ```Input: nums = [1,2,3,4] Output: [24,12,8,6]


**Example 2:**
```Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

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.)

Solution

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int countZero = 0, indexZero = -1;
    int product = 1;
    *returnSize = numsSize;

    int* result = (int*) malloc(numsSize * sizeof(int));
    if (!result) return NULL;  // handle malloc failure

    // First pass: count zeros and compute product
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 0) {
            countZero++;
            indexZero = i;
        } else {
            product *= nums[i];
        }
    }

    if (countZero > 1) {
        for (int i = 0; i < numsSize; i++) {
            result[i] = 0;
        }
    } else if (countZero == 1) {
        for (int i = 0; i < numsSize; i++) {
            result[i] = (i == indexZero) ? product : 0;
        }
    } else {
        for (int i = 0; i < numsSize; i++) {
            result[i] = product / nums[i];
        }
    }

    return result;
}
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> output(n, 1);
        for(int i=1; i<n; i++) {
            output[i] = output[i-1]*nums[i-1];
        }
        int m = 1;
        for(int i=n-1; i>=0; i--) {
            output[i] = m*output[i];
            m *= nums[i];
        }
        return output;
    }
};
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int l = nums.length;
        int[] out = new int[l];
        out[0] = 1; out[l-1] = 1;
        for(int i=1; i<l; i++) {
            out[i] = nums[i-1]*out[i-1];
        }
        int m=1;
        for(int i=l-1; i>=0; i--) {
            out[i] = m*out[i];
            m *= nums[i];
        }
        return out;
    }
}

/**
 * Alternate solution that handles zeros:
 * class Solution {
 *     public int[] productExceptSelf(int[] nums) {
 *         int[] result = new int[nums.length];
 *         int countZero = 0, indexZero = 0, product = 1;
 *
 *         for (int i = 0; i < nums.length; i++) {
 *             if (nums[i] == 0) {
 *                 countZero++;
 *                 indexZero = i;
 *             } else {
 *                 product *= nums[i];
 *             }
 *         }
 *
 *         if (countZero > 1) {
 *             return result;
 *         } else if (countZero == 1) {
 *             result[indexZero] = product;
 *             return result;
 *         } else {
 *             for (int i = 0; i < nums.length; i++) {
 *                 result[i] = product / nums[i];
 *             }
 *         }
 *
 *         return result;
 *     }
 * }
 */
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1 for _ in range(len(nums))]
        prev = 1
        for i in range(len(nums)):
            res[i] = prev
            prev *= nums[i]
        prev = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= prev
            prev *= nums[i]
        return res
Time Complexity: O(n)
Space Complexity: O(1)