C++: Product of Array Except Self

Thought Process

To solve the problem of finding the product of all elements except the current one, we can use a two-pass approach. In the first pass, we calculate the product of all elements to the left of each element and store it in the resultant array. In the second pass, we calculate the product of all elements to the right of each element and multiply it with the previously stored left product in the resultant array. 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
  
        int sz = nums.size();
        vector<int> ans(sz);
  
        ans[0] = 1;
        for(int i=1;i<sz;i++){
            ans[i] = ans[i-1]*nums[i-1];
        }
  
        int right=1;
        for(int i=sz-2;i>=0;i--){
            right = right*nums[i+1];
            ans[i] = ans[i]*right;
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm makes two passes through the array, each taking O(n) time. Therefore, the overall time complexity is O(n).

Space Complexity: O(1) (excluding the output array)

The algorithm uses a constant amount of extra space for variables, and the output array is not counted towards the space complexity.

Code copied!