238. Product of Array Except Self

The idea is to compute the cumulative left products first and store them in the array. And then from the right side compute the cumulative right product and thus compute the final product of the array except self. The total running time is O(2n).

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