Maximum Subarray (LeetCode #53)

Image by Ibrahim Rifath 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

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

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 sometimes.

I’m going to teach you a formula that will let you solve it immediately from here on out.

Let’s get started! 🦾

Understanding the Problem 👷🏻‍♂️

The first thing we should always try to do is understand all the rules for the challenge (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of nums (which have a minimum length of 1)
2. We should find the largest contiguous (which means together in sequence) subarray containing at least one number which has the largest sum
3. We should return that largest sum

Okay, I think that’s enough that we can kick off writing some code.

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.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

So with all of that said, let’s get into it.

Kadane’s Formula 🧮

When trying to solve coding challenge problems, I believe it’s best to memorize patterns instead of solutions to a single problem.

Because of that, it’s probably best if we talk through Kadane’s Formula before writing our code.

This is a super efficient formula commonly used to solve the “maximum subarray” problem (and it technically falls under the “dynamic programming” umbrella).

It’s quite simple. These are the steps:

1. Track the maximum sum you’ve seen
2. Track the current sum so far
3. For each number in the list of nums, add it to the the current sum so far
4. If that new current sum is larger than the maximum sum you’ve seen, set it as the new value for the maximum sum
5. Finally (before continuing to the next iteration of your loop), set the value of the current sum to 0 if it’s current value is less than 0 (negative)

That last bit, the resetting to 0, is where the magic happens for this formula.

While a lot of other maximum sum/product/etc. problems might need a big modification of this formula to work correctly, I promise that understanding the basics of Kadane’s Formula will give you a lot more confidence to approach any of them.

I’ll also 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.

We’ll be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Now that we’ve gone over this formula, let’s get to it!

Setting Up Variables 🤖

The first thing we should do when solving this problem is to go ahead and set up our variables that we just mentioned in the previous section:

Okay, let’s talk about what’s going on here. Why did we set max_total to the first nums value? Why did we use a Python ternary statement for the current_total?

Since our nums list can have a minimum length of 1, we need to be prepared for lists that might looks something like [-1]. In this case, the maximum sum would be -1 which is highly unfortunate. We’d need to just return this.

However, we also can’t allow the current_total to drop below 0 in between each number that we check. Because of that, we should set it to the nums[0] value only if the value is > 0. Otherwise, we might as well just set it to 0 right out of the gate.

If we had a list of nums that looked something like [-1, 4, 0, 2], subsequent iterations of the loop would overwrite that initial -1 value for max_total.

Make sense?

If not, it will hopefully become even clearer as we continue.

Building Our Loop 🔁

Okay, we have our initial variables set up. The next thing we should do is to build out our loop:

The reason we have to use a range loop here is because we want to start at index 1 instead of 0. We already used number 0 from our nums list up above when setting up our initial variables, remember?

Setting nums[i] to the num variable is just me making it easy to reference the value later by an easy-to-remember name.

From here, all we need to do each loop is:

1. Add num to the current_total
2. Check if current_total is greater than max_total
3. Reset current_total to 0 if it’s current value is < 0

This is what that will look like in code form:

There we go. 🔥

This solution will run in O(n) time complexity (since it’s iterating straight through the list of nums) and use O(1) space complexity (since we’re only ever using two variables to track max_total and current_total no matter how long the list of nums is).

Conclusion

I hope you learned something useful while solving this problem!

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 great book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)