Product of Array Except Self - LeetCode Solution in C++, Java, Python

1. Introduction

The "Product of Array Except Self" problem requires computing an array where each element is the product of all elements in the input array except itself, without using division. This problem tests the ability to manipulate arrays and use prefix and suffix products.

2. Problem

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.

3. Solution in C++

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);

    int left = 1;
    for (int i = 0; i < n; i++) {
        answer[i] *= left;
        left *= nums[i];
    }

    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }

    return answer;
}

Explanation:

1. Initialize an array answer with size n and fill it with 1s.

2. Traverse the array from left to right, multiplying each element in answer by the product of all elements to the left of nums[i].

3. Traverse the array from right to left, multiplying each element in answer by the product of all elements to the right of nums[i].

4. The final answer array contains the product of all elements except itself for each index.

4. Solution in Java

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    Arrays.fill(answer, 1);

    int left = 1;
    for (int i = 0; i < n; i++) {
        answer[i] *= left;
        left *= nums[i];
    }

    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }

    return answer;
}

Explanation:

1. Create an array answer and fill it with 1s.

2. First, calculate the left product for each element and store it in answer.

3. Then, calculate the right product for each element and multiply it with the corresponding value in answer.

4. The answer array will contain the required product of all elements except the current one for each index.

5. Solution in Python

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n

    left = 1
    for i in range(n):
        answer[i] *= left
        left *= nums[i]

    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]

    return answer

Explanation:

1. Initialize answer with ones.

2. Calculate the left products and store them in answer.

3. Calculate the right products and multiply them with the corresponding elements in answer.

4. answer now contains the products of all elements except the current one for each index.