[LintCode] #50 Product of Array Exclude Itself

Thinking:
1) brute force O(n^2)
2) generate left, right array: for [1,2,3], left=[1,1,2], right=[6,3,1] O(n) + O(n) space
3) optimization: only use left array

public class Solution {
    /**
     * @param A: Given an integers array A
     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        // write your code
        ArrayList<Long> result = new ArrayList<Long>();
        if (A == null || A.size() == 0) {
            return result;
        }
        
        Long[] left = new Long[A.size()];
        left[0] = 1L;
        for (int i = 1; i < A.size(); i++) {
            left[i] = left[i - 1] * A.get(i - 1);
        }
        
        Long[] right = new Long[A.size()];
        right[A.size() - 1] = 1L;
        for (int i = A.size() - 2; i >= 0; i--) {
            right[i] = right[i + 1] * A.get(i + 1);
        }
        
        for (int i = 0; i < A.size(); i++) {
            result.add(left[i] * right[i]);
        }
        
        return result;
    }
}