238 Product of Array Except Self

238. Product of Array Except Self

1. Question

Given an array ofn_integers where_n> 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.)

2. Implementation

(1) DP

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] res = new int[n];
        int[] prodFromLeft = new int[n];

        prodFromLeft[0] = 1;

        for (int i = 1; i < n; i++) {
            prodFromLeft[i] = prodFromLeft[i - 1] * nums[i - 1];
        }

        int[] prodFromRight = new int[n];
        prodFromRight[n - 1] = 1;

        for (int i = n - 2; i >= 0; i--) {
            prodFromRight[i] = prodFromRight[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            res[i] = prodFromLeft[i] * prodFromRight[i];
        }
        return res;
    }
}

(2) Follow up

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, 1);
        int temp = 1;
        for (int i = 0; i < n; i++) {
            res[i] = temp;
            temp *= nums[i];
        }

        temp = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= temp;
            temp *= nums[i];
        }
        return res;
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)

Follow up: 时间复杂度O(n), 空间复杂度O(n)