298. Product of Array Except Self

Given an array numsof n integers where n> 1, return an array outputsuch that output[i]is equal to the product of all the elements of numsexcept nums[i].

Example:

Input: [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Code: with extra space:

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        m = collections.defaultdict(list)
        p = 1
        for i, num in enumerate(nums):
            m[i] = p
            p *= num

        p = 1

        for i, num in reversed(list(enumerate(nums))):
            m[i] *= p
            p *= num

        return [m[k] for k in sorted(m.keys())]

Code: without extra space:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int res [] = new int [n];
        int p = 1;

        // multiply left
        for(int i = 0; i < n; i++){
            res[i] = p;
            p *= nums[i];
        }

        // multiply right
        p = 1;
        for(int i = n - 1; i >=0 ; i--){
            res[i]*= p;
            p *= nums[i];
        }

        return res;
    }
}

Code: actually index is the key: so we do not need the extra dictionary

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # m = collections.defaultdict(list)
        res = [0] * len(nums)
        p = 1
        # left
        for i, num in enumerate(nums):
            res[i] = p
            p *= num

        p = 1

        for i, num in reversed(list(enumerate(nums))): # i is also reversed
            res[i] *= p
            p *= num

        return res