C++, O(n) time, O(1) extra space


  • 9
    class Solution {
    public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int k = nums.size();
        vector<int> res(k,1);
        for (int i=1;i<k;i++){
            res[i]=res[i-1]*nums[i-1];
        }
        int temp = 1;
        for (int i=k-1;i>=0;i--){
            res[i]=res[i]*temp;
            temp*=nums[i];
        }
        return res;
    }
    };

  • -1
    T

    I don't think this is O(1) extra space since you are using result vector as a temporary working space for calculating product accumulated from one direction,


  • 0

    I agree what you said, but the problem says (Note: The output array does not count as extra space for the purpose of space complexity analysis.)


  • 0
    Z

    Good alg, I see such a solution for first time(maybe I am naive now), thank you


Log in to reply
 

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