Product of Array Except Self

---

This problem challenges us to find the product of all elements in an array except for the current element, without using division. While the brute-force approach of computing the product of all elements and then dividing by each element is straightforward, it’s not optimal in terms of time or space complexity.

In this article, we’ll explore different approaches to solving this problem efficiently. By the end of this article, you’ll have a better understanding of how to tackle this problem and be equipped with several approaches to optimize your solution.

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].

You must write an algorithm that runs in O(n) time and without using the division operation.

---

Approach 1: Brute Force

1. We will simply use two nested loops to calculate the product of all elements except the current element in the input array.

2. Store the product in a new array and return that array.

// ES6 Arrow Function
const productExceptSelf = nums => {
    const result = [];
    for(let i = 0; i < nums.length; i++) {
        let product = 1;
        for(let j = 0; j < nums.length; j++) {
            if(i !== j) {
                product *= nums[j];
            }
        }
        result.push(product);
    }

    return result;
}

Time Complexity: O(N²)

Space Complexity: O(N)

Note: This might be a very straightforward solution to this problem but it’s not efficient for larger inputs.

---

Approach 2: Two-Pass Solution

1. Firstly, We find the product of all elements to the left of each element in the input array in the first pass.

2. Then we find the product of all elements to the right of each element in the second pass.

3. Then, multiply the left and right products to get the final product.

// ES6 Arrow Function
const productExceptSelf = nums => {
    const result = [];

    // First Pass
    let product = 1;
    for(let i = 0; i < nums.length; i++) {
        result[i] = product;
        product *= nums[i];
    }

    // Second Pass
    product = 1;
    for(let i = nums.length - 1; i >= 0; i--) {
        result[i] *= product;
        product *= nums[i];
    }

    return result;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Approach 3: Prefix and Suffix Products

1. In this approach, we calculate and store the prefix products in one array and suffix products in another array.

2. Prefix Products- The product of all elements up to each element in the input array.

3. Suffix Products- The product of all elements after each element in the input array.

4. Then, multiply the corresponding prefix and suffix products to get the final product.

// ES6 Arrow Function
const productExceptSelf = nums => {
    const prefix = [], suffix = [], result = [];

    // calculate prefix products
    prefix[0] = 1;
    for(let i = 1; i < nums.length; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }

    // calculate suffix products
    suffix[nums.length - 1] = 1;
    for(let i = nums.length - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }

    // product of suffix and prefix to find final result
    for(let i = 0; i < nums.length; i++) {
        result[i] = prefix[i] * suffix[i];
    }

    return result;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Approach 4: Optimized Prefix and Suffix Products

The optimized prefix and suffix products approach involves finding the prefix and suffix products in place by using the output array to store the prefix products and a variable to store the suffix products.

// ES6 Arrow Function
const productExceptSelf = nums => {
    const result = [];
    let product = 1;

    // Find the prefix products and store them in the output array
    result[0] = 1;
    for(let i = 1; i < nums.length; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Find the suffix products in place and multiply them with the prefix products 

    for(let i = nums.length - 1; i >= 0; i--) {
        result[i] *= product;
        product *= nums[i];
    }

    return result;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. So go ahead, and try these approaches out. Just don’t forget to bring your coffee, because you’ll be amazed at how fast your computer can run when it’s not sleeping on the job.

Problem - Leetcode 238