Product of Array Except Self

Problem Statement: Given an array of integers, return an array such that output[i] is equal to the product of all the elements of the input array except nums[i].

Algorithm Explanation:

1. Create two arrays: one for storing the product of elements to the left and one for the right.

2. Traverse the array from left to right and fill the left products.

3. Traverse the array from right to left and fill the right products.

4. Multiply the left and right products for the final output.

Steps:

1. Initialize two arrays left_products and right_products of the same size as the input array.

2. Fill the left_products array with the product of all elements to the left.

3. Fill the right_products array with the product of all elements to the right.

4. Create the output array by multiplying the corresponding elements from left_products and right_products.

Time and Space Complexity:

• Time Complexity: O(N), where N is the number of elements in the array.

• Space Complexity: O(N) for the two additional arrays.

Code Implementation:

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int N = nums.size();
    vector<int> left_products(N, 1);
    vector<int> right_products(N, 1);
    vector<int> output(N);

    for (int i = 1; i < N; i++) {
        left_products[i] = left_products[i - 1] * nums[i - 1];
    }
    for (int i = N - 2; i >= 0; i--) {
        right_products[i] = right_products[i + 1] * nums[i + 1];
    }
    for (int i = 0; i < N; i++) {
        output[i] = left_products[i] * right_products[i];
    }
    return output;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> result = productExceptSelf(nums);
    cout << "Product of array except self: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Java

import java.util.Arrays;
public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int N = nums.length;
        int[] left_products = new int[N];
        int[] right_products = new int[N];
        int[] output = new int[N];

        left_products[0] = 1;
        for (int i = 1; i < N; i++) {
            left_products[i] = left_products[i - 1] * nums[i - 1];
        }
        right_products[N - 1] = 1;
        for (int i = N - 2; i >= 0; i--) {
            right_products[i] = right_products[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < N; i++) {
            output[i] = left_products[i] * right_products[i];
        }
        return output;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] result = productExceptSelf(nums);
        System.out.print("Product of array except self: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Python

def product_except_self(nums):
    N = len(nums)
    left_products = [1] * N
    right_products = [1] * N
    output = [0] * N

    for i in range(1, N):
        left_products[i] = left_products[i - 1] * nums[i - 1]
    for i in range(N - 2, -1, -1):
        right_products[i] = right_products[i + 1] * nums[i + 1]
    for i in range(N):
        output[i] = left_products[i] * right_products[i]

    return output

nums = [1, 2, 3, 4]
result = product_except_self(nums)
print("Product of array except self:", result)