How to Find the Product of All Elements in an Array Except Self - Blind 75 LeetCode

Task description:

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.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Reasoning:

This is an interesting algorithmic task. For each index in the given array, we need to find a product of all elements in the array except the element in the current position. Let’s consider the given example:

I think by looking at the examples above, you got the main idea. An immediate idea can pop up in your head, “let’s multiply all elements in the array, and having it, we can divide it by the element in each position, and it’ll give us the correct result”. It’s the correct way of thinking and it indeed gives us the correct result, but the problem statement says we cannot use division operation.

Let’s continue brainstorming. Another idea could be using something similar to running sum array. Let’s create 2 additional arrays, leftToRigh and rightToLeft. For leftToRigh array we’ll iterate from index = 1 till the end of the array and set the value at each index equal to the multiplication of the current element and the previous value.

        int[] leftToRight = new int[nums.length];
        leftToRight[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
        {
            leftToRight[i] = leftToRight[i - 1] * nums[i];
        }

If we have the input of [1, 2, 3, 4] then the code above gives us [1, 2, 6, 24]

For rightToLeftarray we’ll iterate from index = array.length — 2 till the beginning of the array and set the value at each index equal to the multiplication of the current element and the previous value.

        int[] rightToLeft = new int[nums.length];
        rightToLeft[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--)
        {
            rightToLeft[i] = rightToLeft[i + 1] * nums[i];
        }

If we have the input of [1, 2, 3, 4] then the code above gives us [24, 24, 12, 4]

Now having these arrays we can simply calculate the product of the array except the current element by iterating through each index and multiplying values from leftToRigh and rightToLeft. Here’s an example that will help you to understand the actual logic.

If you struggle to understand the logic try to go through the pictures above one more time.

Let’s have a look at our solution:

    public int[] productExceptSelf(int[] nums)
    {
        int[] leftToRight = new int[nums.length];
        leftToRight[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
        {
            leftToRight[i] = leftToRight[i - 1] * nums[i];
        }

        int[] rightToLeft = new int[nums.length];
        rightToLeft[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--)
        {
            rightToLeft[i] = rightToLeft[i + 1] * nums[i];
        }

        int[] answer = new int[nums.length];
        for (int i = 0 ; i < answer.length; i++)
        {
            int left = i == 0 ? 1 : leftToRight[i - 1];
            int right = i == answer.length - 1 ? 1 : rightToLeft[i + 1];

            answer[i] = left * right;
        }

        return answer;
    }

It works and gives us a decent result:

BUT. Let’s read the task description one more time. At the very bottom, we have a follow-up question — to solve the problem using constant space. Here we used two auxiliary arrays.

Solution:

    public int[] productExceptSelf(int[] nums)
    {
        int[] answer = new int[nums.length];
        Arrays.fill(answer, 1);

        int prev = 1;
        for (int i = 1; i < nums.length; i++)
        {
            answer[i] = prev * nums[i - 1];
            prev = answer[i];
        }

        prev = 1;
        for (int i = nums.length - 2; i >= 0; i--)
        {
            answer[i] *= prev * nums[i + 1];
            prev *= nums[i + 1];
        }

        return answer;
    }

If you carefully read the description you might have noticed that the output array doesn’t count as additional space, it’s a trick. Having input array and output array we still have 2 arrays like leftToRight and rightToLeft we used in our previous solution. We just need to slightly adapt our logic.

The code above gives us almost the same result but uses constant space O(1).

Let me know your thought. See you in my articles!

Also published here.