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


  • 0
    vector<int> productExceptSelf(vector<int>& nums) {
        int arrLen = nums.size();
        vector<int> outputs(arrLen, 1);
    
        // Calculate forward item
        // For outputs(i) = outputs(0)* outputs(1)...outputs(i - 1)
        for (int i = 0; i < arrLen; ++i) {
            if (0 != i) outputs[i] = nums[i - 1] * outputs[i - 1];
        }
    
        int res = 1;
        // Calculate reverse item
        // For outputs(i) = outputs(i)* res, res = nums[i + 1] * nums[i + 2]*... * nums[N - 1]
        for (int i = arrLen - 1; i >= 0; i--) {
            outputs[i] = res * outputs[i];
            res *= nums[i];
        }
        return outputs;
    }
    

Log in to reply
 

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