Product of Array Except Self

Problem Statement

LeetCode Question Link

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.

Solution

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    const int n = nums.size();
    vector<int> ans(n);        // Can also use `nums` as the ans array.
    vector<int> prefix(n, 1);  // prefix product
    vector<int> suffix(n, 1);  // suffix product

    // Calculate prefix products
    for (int i = 1; i < n; ++i)
      prefix[i] = prefix[i - 1] * nums[i - 1];

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

    // Calculate the final product except self
    for (int i = 0; i < n; ++i)
      ans[i] = prefix[i] * suffix[i];

    // Return the result
    return ans;
  }
};

Algorithm steps:

1. Create three vectors:
   • ans: This will store the final result.
   • prefix: This will store the prefix products.
   • suffix: This will store the suffix products.
2. Initialize the size of the vectors as n, the size of the input nums.
3. Calculate the prefix products by iterating through nums from the second element to the last. Store the product of all previous elements in prefix[i].
4. Calculate the suffix products by iterating through nums from the second-to-last element to the first. Store the product of all following elements in suffix[i].
5. Multiply the corresponding elements of prefix and suffix to get the product of all elements except nums[i], and store the result in ans.
6. Return the ans vector.

Time complexity:

• The time complexity of this code is O(n), where n is the size of the input nums. This is because we iterate through the nums vector three times, and each iteration takes linear time.

Space complexity:

• The space complexity of this code is O(n). We use additional space to store prefix, suffix, and ans, each of size n.

This code efficiently computes the product of all elements except self for each element in the input vector nums. There's no significant reduction possible for time or space complexity in this scenario because we need to compute prefix and suffix products to achieve the desired result.