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