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 elements except nums[i] is calculated as follows:

• answer[0] = 2 * 3 * 4 = 24
• answer[1] = 1 * 3 * 4 = 12
• answer[2] = 1 * 2 * 4 = 8
• answer[3] = 1 * 2 * 3 = 6

Example 2:

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

Steps and Explanation

The key to solving this problem efficiently (in O(n) time) without division is to calculate the prefix and suffix products separately. We'll do this in two passes:

1. Prefix Pass: Create an array prefix_prod where prefix_prod[i] stores the product of all elements before nums[i]. prefix_prod[0] will be 1 (there are no elements before the first element).

2. Suffix Pass: Create an array suffix_prod where suffix_prod[i] stores the product of all elements after nums[i]. suffix_prod[n-1] will be 1 (there are no elements after the last element).

3. Result: The final result answer[i] is simply prefix_prod[i] * suffix_prod[i].

Code

#include <vector>

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

    // Prefix pass
    for (int i = 1; i < n; ++i) {
        prefix_prod[i] = prefix_prod[i - 1] * nums[i - 1];
    }

    // Suffix pass
    for (int i = n - 2; i >= 0; --i) {
        suffix_prod[i] = suffix_prod[i + 1] * nums[i + 1];
    }

    // Calculate the final result
    for (int i = 0; i < n; ++i) {
        answer[i] = prefix_prod[i] * suffix_prod[i];
    }

    return answer;
}

Complexity

• Time Complexity: O(n), as we iterate through the array three times.
• Space Complexity: O(n), to store the prefix_prod, suffix_prod, and answer arrays. We could optimize space slightly by not creating prefix_prod and suffix_prod explicitly and storing intermediate results directly in answer, but this would make the code less readable.