Product of Array Except Self Blind 75 LeetCode Questions

Photo by Chris Liverani on Unsplash

Task description:

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:

Getting the result for index = 0

Getting the result for index = 1

Getting the result for index = 2

Getting the result for index = 3

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 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 equals to multiplication of current element and previous value.

Construction of leftToRight array

If we have input of [1, 2, 3, 4] then code above give 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 equals to multiplication of current element and previous value.

Construction of rightToLeft array

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

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

Calculating result for index = 0

Calculating result for index = 1

Calculating result for index = 2

Calculating result for index = 3

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

Let’s have a look at our solution:

It works and give us 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:

Solution using constant O(1) space

If you carefully read the description you might have noticed that 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.

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

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

Level Up Coding

Thanks for being a part of our community! Before you go:

• 👏 Clap for the story and follow the author 👉
• 📰 View more content in the Level Up Coding publication
• 🔔 Follow us: Twitter | LinkedIn | Newsletter

🚀👉 Join the Level Up talent collective and find an amazing job