Product of Array Except Self

1package pkg5leetcode;2 3/*4 * LeetCode 238: Product of Array Except Self  (Medium)5 * ----------------------------------------------------6 * Return an array where output[i] = product of all elements except nums[i],7 * WITHOUT using division and in O(n).8 *9 * APPROACH: prefix products (left pass) then multiply by suffix products (right pass).10 * COMPLEXITY: Time O(n), Space O(1) extra (output array aside).11 */12import java.util.*;13 14public class leetcode6ProductExceptSelf {15 16    static int[] productExceptSelf(int[] nums) {17        int n = nums.length;18        int[] res = new int[n];19        res[0] = 1;20        for (int i = 1; i < n; i++) res[i] = res[i - 1] * nums[i - 1];   // prefix21        int suffix = 1;22        for (int i = n - 1; i >= 0; i--) {                               // suffix23            res[i] *= suffix;24            suffix *= nums[i];25        }26        return res;27    }28 29    public static void main(String[] args) {30        check(Arrays.equals(productExceptSelf(new int[]{1, 2, 3, 4}), new int[]{24, 12, 8, 6}), "basic");31        check(Arrays.equals(productExceptSelf(new int[]{-1, 1, 0, -3, 3}), new int[]{0, 0, 9, 0, 0}), "with zero");32        System.out.println("leetcode6ProductExceptSelf: all tests passed");33    }34 35    static void check(boolean cond, String name) {36        if (!cond) throw new AssertionError("FAILED: " + name);37        System.out.println("  PASS " + name);38    }39}