Product of Array Except Self (LeetCode #238)

Image by Ben Wicks on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Maximum Product Subarray.

Introduction

Hey fam. I’m glad you’ve joined in for this code challenge walk through.

If you’re looking for a solution to the LeetCode Product of Array Except Self code challenge, this is the place you’ve been looking for. 👏🏻

This is a question from the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for coding challenge-style interviews.

If this one’s been giving you a hard time and your existing solution on LeetCode isn’t passing, don’t worry — we’ll get you sorted quick. Everyone that codes is constantly learning.

With all of that said, let’s just jump into it. ☕️

Initial Setup 🏗

You might have tried a variety of different ways to solve this problem already, but I’d guess that none of them passed all the test cases on LeetCode. That’s why you’re here hanging out with me.

The key to this problem is that we want to make sure that the solution runs in O(n) time complexity so we don’t have timeouts.

In order to achieve that, we can’t have any nested loops.

Before we start coding, let’s go ahead and break down the rules for the problem (the first step in the famous Polya’s Problem Solving Techniques):

1. We’ll take in a list of nums where each value is an integer
2. We should return a list of answers where each i index position is the product of every other integer in the list except the one in nums[i]

Interesting. In other words, if we take in a list like [2, 3, 1, 5, 2], we should return a list of answers like [30, 20, 60, 12, 30].

This is because:

1. 30 = 3 x 1 x 5 x 2
2. 20 = 2 x 1 x 5 x 2
3. 60 = 2 x 3 x 5 x 2
4. 12 = 2 x 3 x 1 x 2
5. 30 = 2 x 3 x 1 x 5

Building Two Multiplication Lists 🔁 🔁

If we have a list of numbers we want to multiply, does the answer depend on which order we multiply them in (e.g. 2 x 10 x 30 versus 30 x 10 x 2)?

No, it doesn’t!

We can leverage this fact to “divide” and multiply. What I mean by this is that we can create a list of numbers being multiplied from left to right and then another one of numbers being multiplied from right to left.

Using these two, we can multiply the numbers on either side of the index i to get the final answer. This should all be able to be done in O(n) time complexity.

Okay, let’s talk code.

First, let’s build a list of numbers where the product is the current answer of multiplying every number progressively from left to right:

See how this works? I’m going to be coding this part with normal loops because it’s easier for people coming from all different languages to understand, but those of you more familiar with Python can try modifying it to use list comprehension syntax.

Here’s what it looks like (inside the product_except_self function we’re going to use for the rest of the problem):

You can likely simplify this down if you want. I’m writing my code to maximally clear with what’s going on here, even if it’s a bit longer.

The next thing we need to do is use this same technique to create a list of products multiplying from right to left. I’ll create a new empty list called right_to_left, set it to an empty list, and use a second loop to multiply:

FYI, that range(len(nums) — 1, -1, -1) syntax is Python’s way of saying, “iterate over the numbers from the length of the nums list minus one, go down to the number above -1, and decrease by -1 every loop (instead of increasing by 1).

Again, there are a lot of ways to simplify this code (and you should try it when we’re done), but I’m writing this to be super clear to you as the reader about what’s going on here.

The reason we need to use .reverse() on the right_to_left list after we’re done (which reverses the list in place) is because we were building it up in reverse (like [4], [4, 10], [4, 10, 30], etc.). In order for us to use it to get our final answer, we needed to flip it around.

With these two lists built, we now have the information we need to build our final results list. 🙌🏻

Building Our Final Results List 🏆

Believe it or not, we’re past the hardest part of this problem. All we need to do now is to iterate over the nums list one last time and, for every index that’s not 0 or len(nums) — 1, set the index to left_to_right[i — 1] * right_to_left[i + 1].

In other words:

Said another way, here’s the process of building the answers list from those same example lists above:

In code form, this is what this algorithm ends up looking like with the rest of the function we’ve already written:

Even though we iterate over the nums list multiple times, none of the operations are nested. This means that this solution runs in O(n) time complexity with a space complexity of O(n).

Conclusion

It’s done! Congrats! 🙌🏻

I really hope you also picked up some useful knowledge along the way.

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)