Blind 75 - problem 4 : Product of Array Except Self

Problem Statement 

Product of Array Except Self

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

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation: 
For index 0, the product of all the elements except 1 is 2 * 3 * 4 = 24.
For index 1, the product of all the elements except 2 is 1 * 3 * 4 = 12.
For index 2, the product of all the elements except 3 is 1 * 2 * 4 = 8.
For index 3, the product of all the elements except 4 is 1 * 2 * 3 = 6.

Example 2:

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

---

Optimal Approach

The optimal way to solve this problem is to use two auxiliary arrays: one to store the products of all elements to the left of the current index, and one to store the products of all elements to the right. This approach allows us to compute the result in O(n) time without using division.

• First pass: Populate the result array with the product of all elements to the left of each index.
• Second pass: Multiply the result array by the product of all elements to the right of each index.

This ensures that each element in the final result is the product of all elements except the element at that index.

---

LeetCode-Compatible Code Implementation

C++ Solution

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, 1);

        // Step 1: Compute the product of elements to the left of each index
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Step 2: Compute the product of elements to the right of each index
        int rightProduct = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProduct *= nums[i + 1];
            result[i] *= rightProduct;
        }

        return result;
    }
};

---

Step-by-Step Explanation of Code

1. Initialization: We initialize a result vector of the same size as nums, and populate it with 1. This will store the final products.

2. First pass (Left products):

   • We iterate from left to right, and for each index i, we compute the product of all elements to the left of i. This is stored in result[i].
   • For example, for index i = 2, result[2] will store the product of nums[0] * nums[1].

3. Second pass (Right products):

   • We initialize a variable rightProduct to 1 to keep track of the product of elements to the right of the current index.
   • We iterate from right to left, updating rightProduct and multiplying result[i] by rightProduct to incorporate the product of elements to the right of index i.

4. Final result: The result array now holds the product of all elements except the element at each index.

---

Dry Run / Execution Steps

Input: [1, 2, 3, 4]

1. Left products (first pass):

   • For i = 0: result[0] = 1 (nothing to the left).
   • For i = 1: result[1] = 1 * 1 = 1.
   • For i = 2: result[2] = 1 * 2 = 2.
   • For i = 3: result[3] = 2 * 3 = 6.
   • Result after first pass: [1, 1, 2, 6].

2. Right products (second pass):

   • For i = 2: rightProduct = 4, result[2] = 2 * 4 = 8.
   • For i = 1: rightProduct = 12, result[1] = 1 * 12 = 12.
   • For i = 0: rightProduct = 24, result[0] = 1 * 24 = 24.
   • Result after second pass: [24, 12, 8, 6].

Output: [24, 12, 8, 6]

---

Alternative Approaches & Why Not?

1. Brute Force Approach

• Description: For each element, multiply all other elements in the array to calculate the product.
• Time Complexity: O(n^2) due to nested loops.
• Space Complexity: O(1), no extra space is used.

Why Not?: This approach is inefficient for large arrays because of its O(n^2) time complexity.

2. Division Approach

• Description: Calculate the product of all elements in the array, then for each index, divide the total product by the element at that index.
• Time Complexity: O(n).
• Space Complexity: O(1), if we disregard the output array.

Why Not?: This approach does not handle cases where the array contains zeroes, as division by zero is undefined. Additionally, using division might not always be the best approach.

---

Best Solution & Why It’s Best

Solution Using Two Passes with Left and Right Products

• Time Complexity: O(n), where n is the number of elements in the array. We iterate through the array twice (once from left to right, once from right to left).
• Space Complexity: O(n) because we use an additional array to store the result.

This approach is optimal because it processes the input in linear time, and avoids the pitfalls of division.

Comparison Table:

Approach	Time Complexity	Space Complexity
Brute Force	O(n^2)	O(1)
Division	O(n)	O(1)
Two Passes (Best)	O(n)	O(n)

---

Complexity Analysis

• Brute Force:

  • Time Complexity: O(n^2) because of the nested loops.
  • Space Complexity: O(1) as no extra space is used.

• Division:

  • Time Complexity: O(n) for a single pass through the array.
  • Space Complexity: O(1) if we disregard the output array.

• Two Passes:

  • Time Complexity: O(n) for two passes through the array.
  • Space Complexity: O(n) for the result array.

---

Conclusion

The two-pass solution with left and right products is the best approach to solving the "Product of Array Except Self" problem. It efficiently computes the result in linear time while avoiding the use of division. For similar problems, you can practice with the following:

• LeetCode - Maximum Product Subarray.
• LeetCode - Multiply Strings.