C++ O(n) time, O(1) solution


  • 0
    J
    vector<int> productExceptSelf(vector<int>& nums) {
    	vector<int> result(nums.size(), nums.front());
    	for (int i = 0; i<nums.size() - 1; i++)
    		result[i + 1] = result[i] * nums[i + 1];
    
    	int temp = 1;
    	for (int i = nums.size() - 1; i >= 0; i--) {
    		if (i == 0)
    			result[i] = temp;
    		else
    			result[i] = result[i - 1] * temp;			
    		temp *= nums[i];
    	}
    
    	return result;
    }

  • -1
    G

    Hi, nice code! However, please note your code uses more than O(1) space.


  • 0
    J

    That's true. Actually, it is O(n) space. But, int this problem, the output array does not count as extra space for the purpose of space complexity analysis. So, I can say it is O(1) space.


Log in to reply
 

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