[LeetCode] Product of Array Except Self

The first answer in this link has a nice illustrative explanation.

Suppose the given array is like [nums[0], nums[1], nums[2], nums[3]]. Then the result array is simply the product of corresponding terms (with the same color) of these two arrays:

[                 1,        nums[0], nums[0] * nums[1], nums[0] * nums[1] * nums[2]]

[nums[1] * nums[2] * nums[3], nums[2] * nums[3],        nums[3],                  1]

Have you noticed the regularities :-)

The code is as follows.

 1 class Solution {
 2 public:
 3     vector<int> productExceptSelf(vector<int>& nums) {
 4         int n = nums.size();
 5         vector<int> prod(n, 1);
 6         for (int i = 1; i < n; i++)
 7             prod[i] = prod[i - 1] * nums[i - 1];
 8         for (int i = n - 1, r = 1; i >= 0; r *= nums[i--])
 9             prod[i] *= r;
10         return prod;
11     }
12 };