4 Lines C++ solution, O(n) time O(1) space


  • 3
    J
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size());
        for (int i = 0, prev = 1; i < nums.size(); prev *= nums[i], ++i) ans[i] = prev;
        for (int i = nums.size() - 1, prev = 1; i >= 0; prev *= nums[i], --i) ans[i] *= prev;
        return ans;
    }

  • 0
    A
    This post is deleted!

  • 0
    S

    That's not O(1) space since you're allocating a new vector dependent on the size of the input array. It's O(n) space.


  • 0
    S

    If you mean vector<int> ans(nums.size());, then please refer to the note in the follow-up of the problem. This solution first calculate a wrong answer (stored in ans[]), then fix it.

    (Note: The output array does not count as extra space for the purpose
    of space complexity analysis.)


  • 0
    S

    You're right, sorry I missed that. In general though, I saw the title of your solution as O(1) space, so I was expecting something different :) Good solution though.


  • 0
    S

    I understand your concern. I just fouond a more strictly O(1) space solution. It still used O(n) to return answer, but no need to fix the answer. https://leetcode.com/discuss/47226/my-recursive-solution-o-n-time-o-1-space


  • 0
    S

    Hello shyamguth.
    There is a strictly O(1) extra space solution, regardless of the problem note! Based on the code in the above link, saleymin has got some idea to store the element of input array, and store the output in the input array since the input array will not be reused.

    class Solution {
    public:
    int multiply(vector<int>& nums, int index, int left)
     {
         int right = 1;
         int curr = nums[index];
        if(index < nums.size() -1 )
            right = multiply( nums, index+1, left*curr);
    
        nums[index] = left * right;
        return right *curr;
    }
    
        vector<int> productExceptSelf(vector<int>& nums) {
            multiply(nums,0,1);
            return nums;
        }
    };

  • -2
    A
    This post is deleted!

  • -1
    E

    vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> ans(nums.size());

    int lp = 1;
    int rp = 1;
    
    for (int j = 0; j < nums.size(); ++j)
    	rp *= nums[j];
    
    for (int curIdx = 0; curIdx < nums.size(); ++curIdx)
    {
    	if (curIdx - 1 >= 0)
    		lp = lp * nums[curIdx - 1];
    	if (curIdx + 1 < nums.size())
    		rp = rp / nums[curIdx];
    		ans[curIdx] = lp * rp;
    }
    
    
    return ans;
    

    }


  • 0
    S

    @skw_kevin: It depends on whether you are counting your recursion stack or not :)


Log in to reply
 

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