Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].

Solve itwithout divisionand in O(n).

For example, given[1,2,3,4], return[24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output arraydoes notcount as extra space for the purpose of space complexity analysis.)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length < 2) return new int[0];
        int[] ans = new int[nums.length];

        int[] left = new int[nums.length];
        int[] right = new int[nums.length];

        left[0] = nums[0];
        right[nums.length - 1] = nums[nums.length - 1];

        for (int i = 1; i < nums.length; i++){
            left[i] = left[i - 1] * nums[i];
        }

        for (int j = nums.length - 2; j >= 0; j--){
            right[j] = right[j + 1] * nums[j];
        }

        for (int k = 0; k < nums.length; k++){
            if (k == 0){
                ans[k] = right[k + 1];
            }
            else if (k == nums.length - 1){
                ans[k] = left[k - 1];
            }
            else{
                ans[k] = left[k - 1] * right[k + 1];
            }
        }

        return ans;
    }
}

without extra space

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