O(n) solution without extra space


  • 1
    J

    The main idea is that we can have 2 arrays holding the left and right part.

     111
    2 22
    33 3
    444
    

    With little effort, the 2 arrays can be the input and return vectors.
    And using STL functions, the solution can be very short.

    class Solution {
    public:
    	vector<int> productExceptSelf(vector<int>& nums) {
    		vector<int> ret(nums.size());
    		ret.front() = 1;
    		partial_sum(nums.begin(), nums.end()-1, ret.begin()+1, multiplies<int>());
    		partial_sum(nums.rbegin(), nums.rend()-1, nums.rbegin(), multiplies<int>());
    		transform(nums.begin()+1, nums.end(), ret.begin(), ret.begin(), multiplies<int>());
    		return ret;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.