Example: Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        answer[0] = 1;
        
        // 0    1
        // 1    1 * x[0]
        // 2    (1 * x[0]) * x[1]
        // 3    ((1 * x[0]) * x[1]) * x[2]
        // ...
        // n-2  (x[0] * x[1] * ... * x[n-4]) * x[n-3]
        // n-1  (x[0] * x[1] * ... * x[n-3]) * x[n-2]

        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] * nums[i-1];
        }
        // right = x[n-1]
        // n-2 (x[n-1]) * (x[0] * x[1] * ... * x[n-4]) * x[n-3]

        // right = x[n-1] * x[n-2]
        // n-3 (x[n-1] * x[n-2]) * (x[0] * x[1] * ... * x[n-5]) * x[n-4]

        int right = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            answer[i] = answer[i] * right;
            right = right * nums[i]; 
        }
        return answer;
    }
}