NeetCode 150: Product of Array Except Self

Table of contents

The Problem

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.

The Approach

The goal is to get the product of all the elements in the array except the current element at the current index.

From the above, we are limited to only use multiplication. Breaking down the problem to each index, the desired value for a given index should be the multiplication of all the values to its left & right, except itself.

As such, 2 passes of nums are required;

• Fowards (->): Mutiplies each index with the current multiplication of all indexes to its left, other than itself.
• Backwards (<-): Mutiplies each index with the current multiplication of all indexes to its right, other than itself.

My Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // Create the answer array & fill it with 1s (neutral entry).
        int[] answer = new int[nums.length];
        Arrays.fill(answer, 1);

        // Fowards loop over the array, multiplying the prefix to
        // answer[i] & multiplying prefix by nums[i] (multiply & collect
        // new value).
        int prefix = 1;
        for (int i = 0; i < nums.length; i++) {
            answer[i] *= prefix;
            prefix *= nums[i];
        }

        // Reverse loop over the array, but for the "right-side" values
        // of each index.
        int suffix = 1;
        for (int i = (nums.length - 1); i >= 0; i--) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }
}

Firstly, we initialize answer & set all values to 1 (so that it does not interfere with the multiplication).

We then initialize prefix = 1 for the same reason above. The “prefix” loop;

• Multiplies answer[i] with the multiplication of all preceding indices (i.e. prefix).
• Multiplies nums[i] to prefix.

After this loop (->) completes, all that is left is to loop (<-) again in reverse order to “collect” the multiplication of all succeeding indices (i.e. suffix).