Maximum Product Subarray (LeetCode #152)

Image by Crissy Jarvis 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 Best Time to Buy and Sell Stock.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Maximum Product Subarray problem, you’re in the right spot.

This is a question in 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 interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges from time-to-time.

With that said, let’s get right into it so you can get your solution.

Initial Setup 🏗

Before we write a single line of code, we should try to understand all the rules for the challenge (see: Polya’s Problem Solving Techniques):

1. We’ll be given a list of integers called nums that will be < 1and <= 2 * 10^4
2. The list will not be empty
3. We should find the largest subarray product inside the nums list

That’s good for now. We should be able to get started.

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

I also won’t be talking through “less optimal” solutions. You came here for an answer, right? I’m going to make sure you get a good one.

Let’s do it.

How on Earth?? 🌍

This problem can be a bit of a doozy if you don’t know a few key things to look for. You might have tried to solve it with some nested for loops or another approach like that. I know I did the first time I saw it.

It turns out the key to this problem is that we should use a super modded up Kadane’s algorithm. This algorithm is the answer for the Maximum Sum Subarray problem and revolves around adding each number one-by-one, tracking the largest total sum seen so far, and resetting the current sum value to 0 if it drops below 0. You can read more about this algorithm here.

The problem is that Kadane’s Algorithm doesn’t work right out of the box here. What happens if we multiply by 0? What happens if we have negative numbers?

We’ll get to all of that. Don’t worry, you’ll be a pro by the end.

The answer to this problem revolves around tracking both the current largest number and the current smallest number. This will allow us to multiply by negative numbers and still be able to track the largest products.

Let’s get into the problem and the code. 👨🏻‍💻

The Prep Work 🔥

The first thing we’ll do is to create our initial variables that we’ll use to track and store our data throughout the loop we’re also about to build.

First, we need to add a variable called maximum_product. This will be what we eventually end up returning from our function as the answer. We need to initialize this with the first element in the nums array.

The next thing we need is two variables where we can track the current largest product and current smallest product. We need to initialize both of these to 1 instead of 0 since we’ll be multiplying against them when we start our loop. Using 0 would cause our entire solution to be 0 when we’re done multiplying against it.

This is what this looks like inside the start of the function we’ll use for solving this problem:

Note that this pattern of using 1 as a baseline in code challenges where you’re doing lots of multiplication is very common.

It’s worth tucking that away for a rainy day on another code challenge. 👍🏻

Building Our Loop 🌀

Okay, we’re set to start working on our for loop!

The first thing we need to do is write a loop that iterates over our entire nums list. It will look like this:

Remember earlier when I mentioned that we’ll be tracking the largest and smallest current products for each value? We have the variables now outside the loop, and we need to multiply them inside the loop against the current num.

However, we have a problem. Can you imagine what we’ll now be running into if our nums list looks something like this?

nums = [4, -10, -5, -3, 5, 8, 10, -2, 0, 5, 9]

What happens if we multiply multiple negative numbers together?

Does this mean that we could have our largest_current_product and smallest_current_product values flip-flopping when we multiply by a negative several times?

It does!

The way we compensate is to use the max() and min() helper functions that Python provides us out of the box. Your favorite language probably has something similar.

What we can do is to preserve the largest_current_product value in a temporary variable (more on why in a second) and then set largest_current_product equal to the max of either num, itself multiplied by num, or smallest_current_product multiplied by num.

Including num in this is to ensure that, if we’ve previously multiplied by 0 (in a list of something like [3, 9, 0, 2, 5]), that we reset our value to 2 on the next iteration of the loop since it would be greater than 0.

The smallest_current_product multiplied by num is key here. It’s what allows us to account for multiplying multiple times by negative numbers.

As you can see in the code above, we end up setting the smallest_current_product with the minimum value. We also use temp_largest_current_product here for our multiplication because we just modified the largest_current_product on the line above and can no longer rely on it for the old value.

Finally, we need to also add a line assigning a new maximum to maximum_product which decides between its existing value, num, or largest_current_product:

The last thing we need to is to include a return statement where we return maximum_product from our function.

When we put this all together, this is the final answer that we end up with:

Boom.

This solution runs in O(n) time complexity (as we’re only using a for loop which isn’t nested) and O(1) space complexity (since our variables in memory are constant no matter how big our nums list is).

Conclusion

Congrats on finishing the problem! I know this might have been a tougher one. 😅

Keep an eye out for the rest of these Blind 75 coding challenges articles from me. I’m going to be solving them and publishing these as I go.

Also, feel free to reach out to me on any of 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)