Product of Array Except Self medium

Problem Statement

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.

Example 1

Input: nums = [1,2,3,4] Output: [24,12,8,6] Explanation: The product of all the elements except the first element is 24. The product of all the elements except the second element is 12. The product of all the elements except the third element is 8. The product of all the elements except the fourth element is 6.

Example 2

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Steps

1. Initialization: Create two arrays, prefixProducts and suffixProducts, both of the same size as nums. Initialize prefixProducts[0] to 1 and suffixProducts[nums.length - 1] to 1.

2. Prefix Product Calculation: Iterate through nums from left to right. For each index i, calculate the prefix product prefixProducts[i] by multiplying prefixProducts[i-1] with nums[i-1]. For i=0, prefixProducts[0] remains 1.

3. Suffix Product Calculation: Iterate through nums from right to left. For each index i, calculate the suffix product suffixProducts[i] by multiplying suffixProducts[i+1] with nums[i+1]. For i=nums.length-1, suffixProducts[nums.length-1] remains 1.

4. Result Calculation: Create a result array result. For each index i, calculate result[i] by multiplying prefixProducts[i] and suffixProducts[i].

5. Return: Return the result array.

Explanation

The algorithm efficiently calculates the product of all elements except the current element by breaking the problem into two subproblems: calculating the prefix product and the suffix product. The prefix product at index i gives the product of all elements to the left of i, and the suffix product gives the product of all elements to the right of i. Multiplying these two gives the desired result. This avoids the need for division and achieves linear time complexity.

Code

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts: number[] = new Array(n).fill(1);
    const suffixProducts: number[] = new Array(n).fill(1);
    const result: number[] = new Array(n).fill(0);

    // Calculate prefix products
    for (let i = 1; i < n; i++) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
    }

    // Calculate suffix products
    for (let i = n - 2; i >= 0; i--) {
        suffixProducts[i] = suffixProducts[i + 1] * nums[i + 1];
    }

    // Calculate result
    for (let i = 0; i < n; i++) {
        result[i] = prefixProducts[i] * suffixProducts[i];
    }

    return result;
};

Complexity

• Time Complexity: O(n), as we iterate through the array three times.
• Space Complexity: O(n), due to the use of three arrays (prefixProducts, suffixProducts, and result). While we could potentially optimize space by overwriting the input array, this solution maintains clarity.