238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except 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.)

Solution

left[i] represents nums[0] * ... * nums[i-1]
right[i] represents nums[i+1] * ... * nums[length - 1]
Reasonably defining arrays can make code simple and tidy

Complexity

O(N) O(N)

fllow up: O(N) O(1)

Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        int length = nums.length;
        int[] left = new int[length];
        int[] right = new int[length];
        
        left[0] = 1;
        for(int i = 1; i < length; i++){
            left[i] = left[i-1] * nums[i-1];
        }
        
        right[length - 1] = 1;
        for(int i = length - 2; i >= 0; i--){
            right[i] = right[i+1] * nums[i+1];
        }
        
        int[] res = new int[length];
        for(int i = 0; i < length; i++){
            res[i] = left[i] * right[i];
        }
        return res;
    }
}
class Solution {
    public int[] productExceptSelf(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        int length = nums.length;
        int[] left = new int[length];
        
        left[0] = 1;
        for(int i = 1; i < length; i++){
            left[i] = left[i-1] * nums[i-1];
        }
        
        int right = 1;
        for(int i = length - 2; i >= 0; i--){
            right *= nums[i+1];
            left[i] *= right;
        }
        
        return left;
    }
}