238. Product of Array Except Self

M238ProductOfArrayExceptSelf.java

/**
 * 238. Product of Array Except Self
 * @author Ivan Asonov
 *  *         Date: June 13, 2021
 *  * @see <a href="https://leetcode.com/problems/product-of-array-except-self/">238. Product of Array Except Self</a>
 */
public class M238ProductOfArrayExceptSelf {

    public int[] productExceptSelf(int[] nums) {
        var result = new int[nums.length];
        // calculate right
        var prod = 1;
        result[nums.length - 1] = 1; // we always skip the last digit, to make the calculation correct by default we are
        // assigning 1 to it (otherwise it will be 0, and the result will be incorrect)
        for (var i = nums.length - 1; i > 0; i--) { // we need to calculate the product of all previous digits and
            // since we calculate all right digits we start from the end and went to the beginning
            // keep tracking the total product of all digits except for the last one (i - 1)
            int c = nums[i];
            prod *= c;
            result[i - 1] = prod; // we assign the current product value of the product to the i - 1 cell
        }

        // calculate left, using the original values and already calculated product of rights
        prod = 1;
        for (var i = 1; i < nums.length; i++) { // start with the second element ( i = 1)
            int c = nums[i - 1]; // take the original value
            prod *= c; // multiply it with cached product value (all digits from the beginning)
            result[i] *= prod; // add the updated product to the results calculated on the previous step
        }
        return result;
    }
}