Product of Array Except Self

Problem Description

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.

Intuition

Since product[i] should be the product of all numbers except nums[i], we could break it down into two parts left[i] and right[i] were producted of the left numbers or the right.

The final project[i] is the product of left[i] and right[i].

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        for(int i = 1; i < n; i++){
	        left[i] = left[i-1] * nums[i - 1];
        }
        
        vector<int> ans(n, 1);
        ans[n - 1] = left[n - 1];
        for(int i = n - 2; i >= 0; i--){
	        right[i] = right[i + 1] * nums[i + 1];
	        ans[i] = right[i] * left[i];
        }
        return ans;
    }
};