C++ solution O(1) space, O(n) time. Easy to understand.


  • 0
    V
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n = nums.size();
            vector<int> res(n, 0);
            res[0] = 1;
            // first pass, each element contains product up to and 
            // not including the current element in nums
            for(int i = 1; i < n; i++) {
                res[i] = res[i-1] * nums[i-1]; 
            }
            
            int product = 1;
            for(int i = n-1; i >= 0; i--) {
                res[i] = res[i] * product;
                product = product * nums[i];
            }   
            return res;
        }
    };
    

Log in to reply
 

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