Product of array except self

medium

Last Updated - 27/08/2024

Problem Statement

Given an array of integers, you need to return a new array where each element at index i is the product of all the numbers in the original array except the number at i. You should aim for an efficient solution that avoids using division.

Example 1

Input: array = [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Example 2

Input: array = [0, 1, 2, 3]

Output: [6, 0, 0, 0]

Example 3

Input: array = [1, 0, 3, 4]

Output: [0, 12, 0, 0]

Solution 1: Prefix and Suffix Products

function computeProductWithoutSelf(nums) {
    const n = nums.length;
    const result = new Array(n);

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

    // Calculate suffix products and combine with prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
} 

const array1 = [1, 2, 3, 4];
computeProductWithoutSelf(array1);  //output: [24, 12, 8, 6] 

const array2 = [0, 1, 2, 3];
computeProductWithoutSelf(array2);  //output: [6, 0, 0, 0] 

const array3 = [1, 0, 3, 4];
computeProductWithoutSelf(array3);  //output: [0, 12, 0, 0]

Solution 2: Using Two Passes

function calculateProductExcludingSelf(nums) {
    const n = nums.length;
    const result = new Array(n);

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

    // Calculate suffix products and combine with prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
} 

const array1 = [1, 2, 3, 4];
calculateProductExcludingSelf(array1);  //output: [24, 12, 8, 6] 

const array2 = [0, 1, 2, 3];
calculateProductExcludingSelf(array2);  //output: [6, 0, 0, 0] 

const array3 = [1, 0, 3, 4];
calculateProductExcludingSelf(array3);  //output: [0, 12, 0, 0]

Solution 3: Using Division

function productArrayWithDivision(nums) {
    const n = nums.length;
    const result = new Array(n);

    let totalProduct = 1;
    let zeroCount = 0;

    // Calculate the total product and count zeros
    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) {
            zeroCount++;
        } else {
            totalProduct *= nums[i];
        }
    }

    // If more than one zero, all products are zero
    if (zeroCount > 1) {
        return new Array(n).fill(0);
    }

    // If exactly one zero, set the product at that position to the total product
    if (zeroCount === 1) {
        return nums.map(num => num === 0 ? totalProduct : 0);
    }

    // No zeros, return the product of all elements except self
    return nums.map(num => totalProduct / num);
} 

const array1 = [1, 2, 3, 4];
productArrayWithDivision(array1);  //output: [24, 12, 8, 6] 

const array2 = [0, 1, 2, 3];
productArrayWithDivision(array2);  //output: [6, 0, 0, 0] 

const array3 = [1, 0, 3, 4];
productArrayWithDivision(array3);  //output: [0, 12, 0, 0]

Solution 4: Using a Helper Function for Comparison

function computeProductArrayComparison(nums) {
    const n = nums.length;
    const result = new Array(n);

    let prefixProduct = 1;
    for (let i = 0; i < n; i++) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }

    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

function areArraysEqual(a, b) {
    if (!Array.isArray(a) || !Array.isArray(b)) {
        throw new Error('Both arguments must be arrays');
    }
    
    if (a.length !== b.length) return false;
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) return false;
    }
    return true;
} 

const array1 = [1, 2, 3, 4];
computeProductArrayComparison(array1);  //output: [24, 12, 8, 6] 

const array2 = [0, 1, 2, 3];
computeProductArrayComparison(array2);  //output: [6, 0, 0, 0] 

const array3 = [1, 0, 3, 4];
computeProductArrayComparison(array3);  //output: [0, 12, 0, 0]