Product array puzzle

Given an array, arr[] construct a product array, res[] where each element in res[i] is the product of all elements in arr[] except arr[i]. Return this resultant array, res[].
Note: Each element is res[] lies inside the 32-bit integer range.

Examples:

Input: arr[] = [10, 3, 5, 6, 2]
Output: [180, 600, 360, 300, 900]
Explanation: For i=0, res[i] = 3 * 5 * 6 * 2 is 180.
For i = 1, res[i] = 10 * 5 * 6 * 2 is 600.
For i = 2, res[i] = 10 * 3 * 6 * 2 is 360.
For i = 3, res[i] = 10 * 3 * 5 * 2 is 300.
For i = 4, res[i] = 10 * 3 * 5 * 6 is 900.

Input: arr[] = [12, 0]
Output: [0, 12]
Explanation: For i = 0, res[i] is 0.
For i = 1, res[i] is 12.

Constraints:
2 <= arr.size() <= 10⁵
-100 <= arr[i] <= 100

Approach 01:

#include <vector>

class Solution {
public:
    std::vector<int> productExceptSelf(const std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> result(n, 1);
        int leftProduct = 1;
        int rightProduct = 1;

        // Calculate left products and store in result
        for (int i = 0; i < n; ++i) {
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }

        // Calculate right products and multiply with corresponding left products
        for (int i = n - 1; i >= 0; --i) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return result;
    }
};

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        leftProduct = 1
        rightProduct = 1

        # Calculate left products and store in result
        for i in range(n):
            result[i] = leftProduct
            leftProduct *= nums[i]

        # Calculate right products and multiply with corresponding left products
        for i in range(n - 1, -1, -1):
            result[i] *= rightProduct
            rightProduct *= nums[i]

        return result

Time Complexity:

• Left Product Calculation:

  We iterate through the array once from left to right to calculate the left products, which takes \( O(n) \).

• Right Product Calculation:

  We iterate through the array once from right to left to calculate the right products and update the result, which also takes \( O(n) \).

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity:

• Auxiliary Space:

  The algorithm uses a result array of size \( n \) and a constant amount of extra variables (leftProduct and rightProduct), so the space complexity is \( O(n) \) for the result array.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \).