Product of Array Except Self Problem

This week I want to go back to the roots of my weekly blog posts and go over one of the LeetCode problems. I am doing that not because I have no other things to talk about, I have some more interesting topics on iOS development, but this week I was solving some LeetCode problems on my spare time, as I usually do and stumbled upon problem #238. Product of Array Except Self which I liked solving a lot. As usual, here is the text of the problem with an example:

This problem is actually ranked as Medium level problem on LeetCode and I think it’s fairly so, it took me a good few minutes to realize which way I should go with solving it, but still, I would say it’s on the Easy end of Medium level problems. According to information provided by LeetCode, this question is asked by interviewers at Facebook, Lyft, Amazon, Microsoft, and Apple. But enough of the introduction part, let’s move to the solution of this problem.

The easiest way to solve this problem would be to simply sum up all the numbers in the array and then, while iterating through the numbers, divide this sum by current number, saving the quotient in the new Array. But it’s too easy for Medium level problem and, of course, if we read the Note given to us in the problem, we can see that it asks us not to use division. So this option doesn’t work for us.

Okay, let’s think of another approach, in the given example to get a product except for self for 3, we need to multiply 1, 2 and 4, so we need to multiply product on the left side of “self” with the product on the right side, I wish there was a way to save all the left products and right products in separate arrays and then just save products of this products in final result array and there is!

Let’s start with creating all the variables we will need in future implementation:

Okay, here is our next step:

And finally, we iterate through nums again saving the product into results Array like this:

And don’t forget to return your result:

The Note also mentioned that we should solve it in O(n) time, which we did, there are 2 iterations through nums, which gives us O(2n) ~ O(n).

And here is the final solution attached as a code snippet:

I hope this post helps you understand how to solve this problem better and next time if you face a problem similar to this during your interview you will be ready to gracefully handle it.

Related posts:

I like to think that all of the heartache I suffered and all of the seasons of life I spent in the wrong relationships still had value. I find that value when I seek the lesson in those…